Himanshu Tyagi April 2022 Electrical Communication Engineering

# Compression for Distributed Optimization and Timely Updates

Prathamesh Mayekar

###### Abstract

The goal of this thesis is to study the compression problems arising in
distributed computing systematically.

In the first part of the thesis, we study gradient compression for distributed
first-order optimization. We begin by establishing information theoretic lower
bounds on optimization accuracy when only finite precision gradients are used.
Also, we develop fast quantizers for gradient compression, which, when used
with standard first-order optimization algorithms, match the aforementioned
lower bounds.

In the second part of the thesis, we study distributed mean estimation, an
important primitive for distributed optimization algorithms. We develop
efficient estimators which improve over state of the art by efficiently using
the side-information present at the center. We also revisit the Gaussian rate-
distortion problem and develop efficient quantizers for this problem in both
the side-information and the no side-information setting.

Finally, we study the problem of entropic compression of the symbols
transmitted by the edge devices to the center, which commonly arise in cyber-
physical systems. Our goal is to design entropic compression schemes that
allow the information to be transmitted in a ’timely’ manner, which, in turn,
enables the center to have access to the latest information for computation.
We shed light on the structure of the optimal entropic compression scheme and,
using this structure, we develop efficient algorithms to compute this optimal
compression scheme.

TO

Aai, Baba, and Kshitij

###### Acknowledgements.

This dissertation was made possible by a fellowship by the Ministry of Human
Resource Development, Gov. of India during my first two academic years at
IISc, and a fellowship by Wipro Ltd. during the subsequent three academic
years at IISc. I would also like to acknowledge Robert Bosch Centre for Cyber-
Physical Systems, IISc and SPCOM, 2018 travel grant for the travel support to
the International Symposium on Information Theory (ISIT), 2018. I consider
myself fortunate to have Prof. Himanshu Tyagi as my advisor. He has been
extremely generous with his time and ideas and often held my hand through most
aspects of academic research, such as reading and writing papers, proving
theorems, and preparing research presentations. For instance, before ISIT
2018, he sat through multiple practice talks and gave valuable feedback on
each one of them. Moreover, he stayed with me during all conference
submissions until we submitted the paper; this was often way past midnight.
Without his support and guidance, perhaps this thesis would not have been
possible. I am thankful to my collaborators Prof. Jayadev Acharya, Prof.
Clément Cannone, Prof. Parimal Parag, and Dr. Ananda Theetha Suresh for their
guidance throughout our collaborations. I would also like to thank professors
at IISc and IITB for their excellent teaching. For instance, at IISc, I
thoroughly enjoyed the Information Theory courses by Prof. Himanshu Tyagi, the
Optimization reading group led by Prof. Aditya Goplan’s research group, the
Probability Theory course by Prof. Srikanth Iyer, and the Foundations of Data
Science course by Prof. Siddharth Barman. At IITB, I thoroughly enjoyed the
Game Theory course by Prof. Ankur Kulkarni, the Integer Linear Programming
course by Ashutosh Mahajan, and the Stochastic Processes course by Prof.
Veeraruna Kavitha. The courses at IITB motivated my decision to pursue a
research career, and the courses at IISc became instrumental in my subsequent
research work. I would also like to thank Prof. Nandyala Hemachandra and Prof.
Veeraruna Kavitha at IEOR, IITB, who encouraged me to pursue a career in
academia. My interactions with fellow graduate students enriched my Ph.D.
experience at IISc. I would like to thank Raghava for delving with me into the
nuances of probability and information theory. I would like to thank Sanidhay
for guiding me through the ups and downs of life at IISc in my early graduate
years. I would like to thank Karthik for teaching me how to teach. I want to
thank Saumya for sharing with me “tangocolors.sty”, a customized tex color
style file that I still use for all my presentations. Thanks are also due to
my labmates Aditya, Mishfad, Raghava, Shubham, Siddharth, Sahasranand, Saumya,
and Vaishali whose presence in the lab made my work a lot more enjoyable. I am
already missing those coffee-break conversations. My IEOR batchmates made my
stay in Bangalore a pleasant one. The weekends spent at Anupam’s place made
the highs of graduate life even more enjoyable and the lows bearable. I would
like to thank my parents for their unconditional support, love, and
encouragement throughout my graduate studies. Without their reassuring
presence and many sacrifices, both my undergraduate and graduate education
would not have been possible. I can never thank them enough! I would like to
thank my younger brother Kshitij for patiently listening to all my ramblings
and rants about graduate student life, guiding me through most aspects of life
outside academia, and, in essence, always being the older, wiser one of the
two of us. I hereby declare that this thesis is my own work and has not been
submitted in any form for another degree or diploma at any university or other
institute of higher education. I certify that to the best of my knowledge, the
intellectual content of this thesis is the product of my own work and that all
the assistance received in preparing this thesis and sources have been
acknowledged. Journal Publications:

  1. 1.

P Mayekar and H Tyagi. “RATQ: A Universal Fixed-Length Quantizer for
Stochastic Optimization”, IEEE Transactions on Information Theory 67(5) (pp.
3130 - 3154).

  2. 2.

P Mayekar, P Parag, and H Tyagi. “Optimal source codes for timely updates”,
IEEE Transactions on Information Theory 66(6) (pp. 3714-3731).

Conference Proceedings:

  1. 1.

J. Acharya, C. Canonne, P. Mayekar111Alphabetical Order used for author list.,
and H. Tyagi. “Information-constrained optimization: Can adaptive processing
of gradients help?”, Advances in Neural Information Processing Systems, 2021.

  2. 2.

P Mayekar, A. T. Suresh, and H. Tyagi. “Wyner-Ziv Estimators: Efficient
Distributed Mean Estimation with Side Information”, International Conference
on Artificial Intelligence and Statistics (pp. 3502-3510). PMLR, 2021.

  3. 3.

P Mayekar and H Tyagi. “Limits on gradient compression for stochastic
optimization”. IEEE International Symposium on Information Theory (pp.
2658-2663). IEEE, 2020.

  4. 4.

P Mayekar and H Tyagi. “RATQ: A universal fixed-length quantizer for
stochastic optimization”. International Conference on Artificial Intelligence
and Statistics (pp. 1399-1409). PMLR, 2020.

  5. 5.

P Mayekar, P Parag, and H Tyagi. “Optimal lossless source codes for timely
updates”. 2018 IEEE International Symposium on Information Theory (ISIT).
IEEE, 2018. (Recipient of the Jack Keil Wolf Student Paper Award.)

toc.sectiontoc.sectionContentsContentstoc.section

  1. 1.

Sets

    1. (a)

$\mathbb{R}^{d}$ is the set of $d$ dimensional vectors, where each coordinate
can take any value on the real line.

    2. (b)

$\mathbb{Z}$ is the set of integers.

    3. (c)

$\mathbb{N}$ is the set of positive integers.

    4. (d)

$[n]:=\\{1,\ldots,n\\}$ is the set of number from $1$ to $n.$

    5. (e)

$|\mathcal{X}|$ is the cardinality of a discrete set $\mathcal{X}.$

    6. (f)

$\\{e_{1},\ldots,e_{d}\\}$ is the Euclidean basis of $\mathbb{R}^{d},$ where
$e_{i}$ is a $d$-dimensional vectors with $i$ coordinate equal to $1$ and rest
of the coordinates equal to $0.$

  2. 2.

Random Variables and Events

    1. (a)

pmf is Probability mass function.

    2. (b)

pdf is Probability density function.

    3. (c)

$iid$ is Independent and identically distributed.

    4. (d)

$P(A)$ is Probability of event $A$.

    5. (e)

$\mathbb{E}[Z]$ is Expectation of the random variable $Z$.

  3. 3.

Norms

    1. (a)

$\|x\|_{p}:=\sum_{i\in[d]}(|x(i)|^{p})^{1/p}$ is the $\ell_{p}$-norm of
$x\in\mathbb{R}^{d}$ .

    2. (b)

$\|X\|_{p}=\mathbb{E}\left[|X|^{p}\right]^{1/p}$ is the $L_{p}$ norm of a
random variable $X$.

    3. (c)

Throughout the paper, $q$ denotes the Hölder conjugate of $p$ (that is,
$\frac{1}{p}+\frac{1}{q}=1$).

  4. 4.

Logarithms

    1. (a)

The logarithm to the base 2 is denoted by $\log a$ and the logarithm to the
base $e$ is denoted by $\ln a$. All the information theoretic measures
considered in this paper – such as Entropy, Rényi divergence, Kullback-Leibler
divergence, and Mutual Information – are defined with logarithm to the base 2.

    2. (b)

The iterated logarithms $\log^{*}(a)$ and $\ln^{*}(a)$ are defined as the
number of times $\log$ and $\ln$ must be iteratively applied to $a$ before the
result is at most $1$.

  5. 5.

Maximum and minimum

    1. (a)

We write $a\vee b$ and $a\wedge b$ for $\max\\{a,b\\}$ and $\min\\{a,b\\}$,
respectively.

###  Chapter 0 Overview

The recent years have witnessed a monumental rise in the data available for
machine learning applications. For instance, ImageNet ([21]), a publicly
available image database, has over fourteen million images, all available to
train machine learning models. Closely mimicking the data rise is the
aspiration to build more capable and accurate machine learning models. This,
in turn, has led to the ever-increasing computing power needed to train
sophisticated deep learning models. For instance, the ResNet ([41])
architectures trained on the ImageNet database can have roughly 20-60 million
trainable parameters. One approach to ensure fast training of such
sophisticated models is to employ distributed optimization methods, where at
each iteration, workers quantize and share their updates, stochastic
gradients, with other workers or the center. However, while this distributed
optimization approach has enjoyed popularity recently, the precise effect
quantization has on convergence rates is not entirely understood.

A related problem is that of federated learning ([49]). Federated learning is
a machine learning paradigm where models are built from decentralized data
residing on mobile devices while preserving the privacy of the data. A few of
the devices share their stochastic gradient updates with the center in a
typical iteration of a federated learning algorithm. In low bandwidth
scenarios, efficiently quantizing these updates becomes crucial. Thus,
understanding the tradeoff between the precision to which gradients are
quantized and the convergence rate becomes crucial in designing efficient
federated learning algorithms.

Finally, the problem of timely dissemination of information has become
increasingly important in modern cyber-physical systems. For instance,
consider the problem of control of the network of autonomous vehicles. In such
a setting timely update of the vehicle state becomes exceptionally crucial. In
such problems, designing compression specifically tailored to the application
of timeliness is crucial.

Keeping in mind the applications listed above, the thesis considers the
following three problems:

  1. 1.

Communication-Constrained First-Order Optimization,

  2. 2.

Efficient Quantization for Federated Learning Primitives,

  3. 3.

Source Coding Schemes for Timeliness.

The first two parts of the thesis are dedicated to studying the distributed
optimization scenarios listed above. In the first part of the thesis, we build
a theory for a distributed optimization setting where the stochastic gradients
are quantized to a given precision. The quantization algorithms we develop in
this part improve over the state-of-the-art algorithms in many settings. In
the second part of the thesis, we revisit primitives often used Federated
Learning: 1) Distributed Mean Estimation 2) Gaussian Quantization. We build
communication-efficient primitives for both these problems. In the final part
of the thesis, we design entropic compression schemes to ensure timely update
of information.

####  1 Communication-Constrained First-Order Optimization

In the first part of the thesis, we study a refinement of the classic query
complexity model of Nemirovsky and Yudin ([71]). In our refinement, the
gradient estimates supplied by the first-order oracle are not directly
available to a first-order optimization algorithm but must pass through a
channel, and only the output of the channel is available to the optimization
algorithm. While we introduced this refinement to study the effect of
communication constraints on convergence rate, the channel can also be used to
model various other information constraints such as local differential privacy
constraints and computational constraints.

In Chapter 1, we derive lower bounds on the optimization error of any first-
order optimization algorithm where it only has access to compressed gradients.
In Theorem 4.4 and 4.5, we show that for the optimization of convex and
$\ell_{p}$ lipschitz family, any optimization algorithm using gradients
compressed to $r$ bits would lead to the following blow-up over the classic
convergence rate: for $p\in[1,2)$, we see a blow-up of
$\displaystyle{\sqrt{\frac{d}{\min\\{d,r\\}}};}$ for $p\in[2,\infty]$, we see
a blow-up of $\displaystyle{\left(\sqrt{\frac{d}{d\wedge
2^{r}}}\right)\vee\left(\sqrt{\frac{d^{2/p}}{d\wedge r}}\right),}$ where $d$
is the ambient dimension. Our lower bounds also extend to the class of
strongly convex and $\ell_{2}$ lipschitz function, which were missing in the
literature of information-constrained optimization. For example, in Theorem
4.6, we show that for the optimization of strongly convex and $\ell_{2}$
lipschitz function, any optimization algorithm using gradients compressed to
$r$ bits would lead to a blow-up of at least $\frac{d}{\min\\{d,r\\}}$ over
the classic convergence rate.

In Chapter 1, we also derive lower bounds for local differential privacy
constraints and computational constraints in Theorems 4.1, 4.2, and Theorems
4.3 and 4.7 and 4.8, respectively. In fact, our lower bounds allows us to
establish optimality of the popular random coordinate descent algorithm for
convex and $\ell_{2}$ lipschitz family, when there is a computational
constraint of computing just one coordinate.

Finally, all the lower-bounds derived in Chapter 1 allow for adaptive
processing of gradients, while the previous literature on information-
constrained optimization restricts to non-adaptive protocols. That is, the
channel used to process the gradients at a given iteration can be chosen as a
function of the information received at the previous iteration. However, as we
see in the compressing schemes derived in the next chapters and privacy
protocols employed in the literature, the non-adaptive processing of gradients
is sufficient to match the lower bounds.

Our proof of lower bounds refines the recipe of [5] and reduces the problem of
lower bounding optimization error to that of upper bounding a mutual
information term. The mutual information term then can be bounded by taking
recourse to recent strong data processing inequalities in [3]. The key
observation in our proof is that we only need to bound a coordinate-wise
average mutual information term compared to the larger total mutual
information considered in [5]. This allows our recipe to be applicable in
settings where the recipe in [5] may not be suitable.

In Chapter 2, we focus on developing optimal quantizers to match lower bounds
derived in Chapter 1 for convex and $\ell_{2}$ lipschitz functions and
strongly convex and $\ell_{2}$ lipschitz functions. Since we assume that the
gradient estimates’ have their Euclidean distance almost surely bounded, this
problem essentially reduces to developing efficient quantizers for input
vector $Y$ such that

$Y\leq B^{2}\quad a.s..$

Our main contribution in this chapter is a quantizer RATQ used to quantize
such input vectors $Y$. In Corollary 4.3, we show that employing RATQ to
compress the gradients along with the optimization algorithm projected
stochastic gradient descent (PSGD) requires precision of
$d\log\log\log\log^{*}d$ bits to attain the convergence rate of the classic,
unrestricted setting for convex, or strongly convex, and $\ell_{2}$ lipschitz
function family. This factor differs by only a minuscule
$\log\log\log\log^{*}d$ from the lower bounds of $\Omega(d)$ on the precision
necessary to attain the convergence of classic setting. Moreover, in Corollary
4.5, we show that employing a subsampled version of RATQ along with PSGD leads
to almost optimal convergence rate, thus matching the lower bounds established
in Chapter 1 for both convex and strongly convex functions, which are also
$\ell_{2}$ lipschitz.

In fact, our quantizer RATQ is part of a general family of quantizers called
adaptive quantizers. An adaptive quantizer uses multiple dynamic ranges,
$\\{[-M_{i},M_{i}]:i\in[h]\\}$, to quantize the input. Once a dynamic range is
chosen, the input is quantized uniformly within it using $k$ uniform level. In
designing RATQ, we stumble upon the following formula for the mean square
error of the adaptive quantizer:

$O\left(\frac{\sum_{i\in[h]}M_{i}^{2}.p(M_{i-1})}{(k-1)^{2}}\right),$

where $p(M)$ is the probability of the input vector exceeding the value $M.$
This formula guides the design of all of our subsequent adaptive quantizers.

Before adaptively quantizing an input, RATQ first preprocesses the input by
randomly rotating it. Random rotation allows the input data to be "evenly"
distributed across all the coordinates and gives us a handle over the data
distribution. This classic idea of Random rotation is also crucial to many of
our subsequent quantizers.

Then in Chapter 2, we relax the almost sure assumption on gradient estimates
noise and study a general noise model for noisy gradient estimate where the
expected Euclidean norm square of the estimates’ output is bounded, termed the
mean square noise model. We show the theoretical limitations imposed by
quantizers for such noise models that do not quantize the norm carefully. We
do this by deriving a lower bound on optimization error in Theorems 5.3 and
5.4, when a popular class of quantizers that quantize the gradient norm
uniformly is employed. Our lower bound relies on a novel heavy-tailed
construction which may be of independent interest. We then present a fixed-
length, gain-shape variant of our quantizer RATQ, termed A-RATQ. In A-RATQ,
the norm (the gain) of the input is quantized by employing another adaptive
quantizer and the input normalized by the norm (the shape) is quantized by
employing RATQ. In Corollaries 5.7 and 5.9, we show that A-RATQ along with
PSGD almost matches the best possible performance for this mean square noise
model. Finally, we present a variable-length update to A-RATQ. This variable-
length version further improves the performance of A-RATQ but only satisfies
the precision constraint in expectation.

In Chapter 3, we develop quantizers to match the lower bounds for
communication-constrained optimization of convex and $\ell_{p}$ lipschitz
family. Our results in this Chapter are primarily restricted to the high-
precision regime. That is, we characterize the minimum precision needed by
optimal quantization and optimization algorithms so that optimization with
compressed gradient achieves the convergence of the classic, unrestricted
setting. In Theorem 4.1, we show that for optimization of convex and
$\ell_{p}$ lipschitz family with compressed gradients, if the gradients are
compressed to a precision of $d^{2/p}\vee\log d$, for $p\in[2,\infty],$ and
$d$, for $p\in[1,2)$, we can attain the convergence rate of the classic,
unrestricted setting. The necessity of this precision follows from the lower
bound on optimization error derived in Chapter 1; for sufficiency, we
construct new quantizers. For $p\in[2,\infty],$ we propose a Quantizer SimQ+
which along with PSGD exactly matches the lower bounds for $p=2$ and
$p=\infty$, and is only a logarithmic factor away from the lower bound for
$p\in(2,\infty)$. Interestingly, for $p=\infty$, compressing the gradients to
only $\log d$ bits using SimQ+ and then employing PSGD with compressed
gradients is sufficient to achieve the convergence of the classic case. Thus,
this improves upon the precision required by RATQ and PSGD,
$d\log\log\log\log^{*}d,$ in the high-precision regime. For $p\in[1,2),$ we
propose another variant of RATQ, which, combined with appropriate mirror
descent algorithms, is almost optimal.

In its simplest form, SimQ+ represents the input in terms of the corner points
of the $\ell_{1}$ ball containing it. To achieve further compression, SimQ+
uses a “type” based compression technique. We will use this type-based
compression idea in some of our later schemes, too.

####  2 Efficient Quantization for Federated Learning Primitives

In Chapter 4, we study the primitive of distributed mean estimation. This
primitive is a crucial subroutine in distributed learning scenarios when the
server uses the average of updates from multiple clients. [88] considered a
version of this problem where $n$ clients communicate a quantized version of
their update to the server, where the total precision of the quantized version
can be at the most $r$ bits. The center uses the quantized versions from all
the clients to estimate the sample mean of the data. A lower bound of
$\displaystyle{\frac{d}{nr}}$ was established on the mean square error (MSE)
between the actual sample mean and the estimated sample mean. [88] also
proposed a quantization procedure that matches this lower bound up to
$\log\log d$ factor. In Theorem 4.1, we derive the best known upper bound on
MSE, which is tight up to a $\log\ln^{*}d$ factor from the lower bound. Our
scheme uses the quantizer RATQ from Chapter 2.

Then, motivated by the fact that in many federated learning scenarios, the
server also has access to some side-information, we propose and study
distributed mean estimation where the server also has access to side-
information. We study this problem in two different settings: 1) the distance
between the update and the side-information is known to the clients and the
server; 2) the distance between the update and the side-information is unknown
to all, the universal setting. For the first setting, we propose a quantizer
RMQ and show in Theorem 5.4 that it results in an overall MSE of roughly
$\frac{d\Delta^{2}}{nr}$, where $\Delta^{2}$ is the distance between the
client’s update and the respective side-information at the server. Thus, we
can break the lower bound of no side-information setting using side-
information, as long as $\Delta\leq 1$. Our quantizer RMQ first preprocesses
the update using Random rotation like RATQ and then uses a modulo quantizer
for each coordinate. Coming to the unknown setting, we propose a quantizer
RDAQ and show in Theorem 6.4 that results in an overall MSE of roughly
$\frac{d\Delta}{nr}$. Thus, we can again break the lower bound of the no side-
information case with accurate side-information. Our quantizer RDAQ first
preprocesses the updates by randomly rotating them and then uses the idea of
correlated sampling to provide MSE bounds dependent on the distance without
the knowledge of the distance.

In Chapter 5, we the revisit the Gaussian rate-distortion problem and show
that the quantization schemes from earlier Chapters are almost optimal while
being efficient for this problem. In Theorem 3.1, we show that a subroutine of
RATQ attains a rate very-close to the Gaussian rate-distortion function while
being computationally feasible relative to the optimal coding scheme. In
Theorem 4.1, we show that the simple modulo quantizer achieves a rate close to
the rate-distortion function for the version of Gaussian rate-distortion
problem with side–information.

####  3 Source Coding for Timeliness

In the final part of the thesis, we study a source coding problem to
facilitate the timely dissemination of information. This study focuses on
communication systems where the time to transmit information is directly
proportional to its code length, and the receiver needs to be apprised about
only the latest information. Based on the age of information metric proposed
in [50], we measure the performance of our schemes by the average age of
information. For information received at time $t$ which was generated at time
$U(t)\leq t$, the age of information at the receiver is $t-U(t).$ Our goal is
to come up with coding schemes which minimize the average age

$\limsup_{T\to\infty}\frac{1}{T}\sum_{t=1}^{T}t-u(t).$

In Theorem 3.2, we show that the average age equals

$\mathbb{E}\left[L\right]+\frac{\mathbb{E}\left[L^{2}\right]}{2\mathbb{E}\left[L\right]}-\frac{1}{2}.$

Our proof relies on the modification of the standard renewal reward theorem.
We then show in Example 3.5 that standard prefix-free coding schemes such as
Shannon codes can be suboptimal by as far as $O(\log|\mathcal{X}|)$ for these
problems, where $|\mathcal{X}|$ is the cardinality of the information. Our
main result is Theorem 5.1, where we show that the optimal source coding
scheme for minimizing average age is Shannon coded corresponding to
distribution, which is a tilting of the original distribution. Our proof
relies on linearizing the average cost, which, in turn, relies on a
variational formula for $L_{p}$ norm of a random variable.

We then extend our recipe of linearizing the cost and identifying the
structure of optimal coding schemes to design source coding schemes to
minimize the average delay. In Theorem 7.4, we show that the optimal source
coding scheme here, too, is a Shannon code for the tilting of the original
distribution.

##  Part 1 Communication-Constrained First-Order Optimization

###  Chapter 1 Lower Bounds for Information-Constrained Optimization

####  1 Synopsis

We revisit first-order optimization under local information constraints such
as communication, local privacy, and computational constraints limiting access
to a few coordinates of the gradient. In this setting, the optimization
algorithm is not allowed to directly access the complete output of the
gradient oracle, but only gets limited information about it subject to the
local information constraints. We consider optimization for both convex and
strongly convex functions and obtain tight or nearly tight lower bounds for
the convergence rate under all three information constraints.

The results presented in this chapter are from [2].

####  2 Introduction

Distributed optimization has emerged as a central tool in federated learning
for building statistical and machine learning models for distributed data. In
addition, large scale optimization is typically implemented in a distributed
fashion over multiple machines or multiple cores within the same machine.
These distributed implementations fit naturally in the oracle framework of
first-order optimization (see [71]) where in each iteration a user or machine
computes the gradient oracle output. Due to practical local constraints such
as communication bandwidth, privacy concerns, or computational issues, the
entire gradient cannot be made available to the optimization algorithm.
Instead, the gradients must be passed through a mechanism which, respectively,
ensures privacy of user data (local privacy constraints); or compresses them
to a small number of bits (communication constraints); or only computes a few
coordinates of the gradient (computational constraints). Motivated by these
applications, in this chapter, we derive lower bounds on first-order
optimization under such constraints. While our focus in the rest of the
chapters would be to achieve these lower bounds for communication constraints.

When designing a first-order optimization algorithm under local information
constraints, one not only needs to design the optimization algorithm itself,
but also the algorithm for local processing of the gradient estimates. Many
such algorithms have been proposed in recent years; see, for instance, [24],
[1], [6], [33], [86], [37], and the references therein for privacy
constraints; [83], [9], [88], [52], [28], [78], [58], [4], [17], [46], [82],
[35], [38] and the references therein for communication constraints; [73, 80]
for computational constraints. However, these algorithms primarily consider
_nonadaptive_ procedures for gradient processing (with the exception of [28]):
that is, the scheme used to process the gradients at any iteration cannot
depend on the information gleaned from previous iterations. In this chapter,
we derive lower bounds for optimization under a much larger class of adaptive
gradient processing protocols. As a result, we answer the following open
question in this part of the thesis.

Can adaptively processing gradients improve convergence in information-
constrained optimization?

For optimization of both convex and strongly convex function families and
under the three different local constraints mentioned above – local privacy,
communication, and computational – we answer this question in the negative.

That is, adaptive processing of gradients has no clear advantage over non-
adaptive processing for convex or strongly convex optimization under
information-constraints.

#####  1 Main contributions

We model the information constraints using a family of channels $\mathcal{W}$;
see Section 3 for a description of the channel families corresponding to our
constraints of interest. We consider first-order optimization where the output
of the gradient oracle must be passed through a channel $W$ selected from
$\mathcal{W}$. Specifically, the gradient is sent as input to this channel
$W$, and the algorithm receives the output of the channel. In each iteration
of the algorithm, the channel to be used in that iteration can be selected
adaptively based on previously received channel outputs by the algorithm; or
channels to be used throughout can be fixed upfront, nonadaptively. The
detailed problem setup is given in Section 1. We obtain general lower bounds
for optimization of convex and strongly convex functions using $\mathcal{W}$,
when adaptivity is allowed. These bounds are then applied to the specific
constraints of interest to obtain our main results.

In terms of overall contribution of this part of this thesis, we show that
adaptive gradient processing does not help for some of the most typical first-
order optimization problems under information constraints. Namely, we prove
that for most regimes of local privacy, communication, or computational
constraints, adaptive gradient processing has nearly the same convergence rate
as nonadaptive gradient processing for both convex and strongly convex
function families. As a consequence, this shows that the nondaptive LDP
algorithms from [24] and nonadaptive compression protocols we develop in
Chapters 2 and 3 are (nearly) optimal for private and communication-
constrained optimization, respectively, even if adaptive gradient processing
is allowed. In another direction, under computational constraints, where we
are allowed to compute only one gradient coordinate, we show that standard
Random Coordinate Descent ($cf.$ [15, Section 6.4]), which employs uniform
(nonadaptive) sampling of gradient coordinates, is optimal for both the convex
and strongly convex function families. This proves that adaptive sampling of
gradient coordinates does not improve over nonadaptive sampling strategies.

#####  2 Remarks on techniques

Without information constraints, [5] provides a general recipe for proving
oracle complexity lower bounds for convex optimization. Specifically, it
reduces optimization problems with a first-order oracle to a mean estimation
problem whose probability of error is lower bounded using Fano’s method ($cf.$
[95]). While our work, too, relies on a reduction to mean estimation, we
deviate from the prior approach, using Assouad’s method instead to prove lower
bounds for various function families. This different approach, in turn,
enables us to derive lower bounds for adaptive processing of gradients. We
then combine our Assouad’s type reduction with upper bounds on mutual
information derived in [3], which crucially hold for adaptive protocols.

We note that the prior work in information-constrained optimization –
primarily, locally private optimization – concerned itself with the family of
convex functions, with no lower bounds known for the more restricted family of
_strongly convex_ functions, even for nonadaptive gradient processing
protocols. The key obstacle is the fact that during the reduction from
optimization to mean estimation, the known hard instance for the strongly
convex family, even when analyzed for nonadaptive protocols, leads to an
estimation problem using adaptive protocols; and thus the lack of known lower
bounds for adaptive information-constrained estimation prevented this approach
from succeeding. In more detail, this hard instance has gradients that can
depend on the query point which in turn can be chosen based on previously
observed channel outputs, an issue which does not arise in the case of the
convex family where the lower bounds are derived using affine functions for
which the gradients do not depend on the query point. We manage to circumvent
this issue by relying on our different Assouad-type reduction.

#####  3 Prior work

The framework we consider can be viewed as an extension of the classical query
complexity model in [71]. We refer the reader to textbooks and monographs [70,
73, 15] for a review of the basic setup. In the information-constrained
setting, motivated by privacy concerns, [24] consider the problem where the
gradient estimates must pass through a locally differentially private (LDP)
channel. However, in their setting the LDP channels for all time steps are
selected at the start of optimization algorithm – in other words, the channel
selection strategy is nonadaptive. In contrast, we allow for adaptive channel
selection strategies (as well as other information constraints); as a result,
the lower bounds established in these papers do not apply to our setting, and
are more restrictive than our bounds. The results of Duchi and Rogers [26] for
Bernoulli product distributions could be combined with our construction to
obtain tight lower bounds for optimization in $p\in[1,2]$ under LDP
constraints, but would not extend to the entire range of $p$. The work of
Braverman, Garg, Ma, Nguyen, and Woodruff [14] on communication constraints,
also for $p\in[1,2]$, is relevant as well; however, their bounds on mutual
information cannot be applied directly, as their setting (Gaussian
distributions) would not satisfy our almost sure gradient oracle assumption.
[28] provide adaptive quantization schemes for convex and $\ell_{2}$ Lipschitz
function family. While the worst-case convergence guarantees for the
quantizers in [28] are similar to those in [9], it shows some practical
improvements over the state-of-the-art for some specific problem instances.
This suggests that while adaptive quantization may not help in the worst case
for non-smooth convex and strongly convex optimization, it may be useful for a
smaller subclass of convex optimization problems.

##### Organization

The rest of the chapter is organized as follows. After formally introducing in
Section 3 the setting, the function classes considered (convex and strongly
convex), and the information constraints we are concerned with, we state and
discuss our lower bounds in Section 4. Proofs of these lower bounds are given
in Section 5.

####  3 Setup and preliminaries

#####  1 Optimization under information constraints

Algorithm $\pi$First OrderOracle OUpdate $x_{t}$$x_{t}$$\hat{g}(x_{t})$ (a)
Classical first-order optimization

Algorithm $\pi$Update $x_{t}$First OrderOracle
O$x_{t}$$W_{t}$$\hat{g}(x_{t})$$Y_{t}$$Y_{t}\mid\hat{g}(x_{t})\sim
W_{t}(\cdot\mid\hat{g}(x_{t}))$$W_{t}$ (b) Information-constrained
optimization with adaptive gradient processing.

Algorithm $\pi$Update $x_{t}$First OrderOracle
O$x_{t}$$\hat{g}(x_{t})$$Y_{t}$$Y_{t}\mid\hat{g}(x_{t})\sim
W_{t}(\cdot\mid\hat{g}(x_{t}))$$W_{t}$ (c) Information-constrained
optimization with nonadaptive gradient processing.

We consider the problem of minimizing an unknown convex function
$f\colon\mathcal{X}\to\mathbb{R}$ over its domain $\mathcal{X}$ using _oracle
access_ to noisy subgradients of the function. That is, the algorithm is not
directly given access to the function but can get subgradients of the function
at different points of its choice. This class of optimization algorithms
includes various descent algorithms, which often provide optimal convergence
rate among all the algorithms in this class ($cf.$ [71]).

In our setup, gradient estimates supplied by the oracle must pass through a
channel $W$,111A channel $W$ with input alphabet $\mathcal{X}$ and output
alphabet $\mathcal{Y}$, denoted $W\colon\mathcal{X}\to\mathcal{Y}$, represents
the conditional distribution of the output of a randomized function given its
input. In particular, $W(\cdot\mid x)$ is the conditional distribution of the
channel given that the input is $x\in\mathcal{X}$.  chosen by the algorithm
from a fixed set of channels $\mathcal{W}$, and the optimization algorithm
$\pi$ only has access to the output of this channel. The _channel family_
$\mathcal{W}$ represents information constraints imposed in our distributed
setting. In detail, the framework is as follows:

  1. 1.

At iteration $t$, the first-order optimization algorithm $\pi$ makes a query
for point $x_{t}$ to the oracle $O$.

  2. 2.

Upon receiving the point $x_{t}$, the oracle outputs $\hat{g}(x_{t})$, where
$\mathbb{E}\left[\hat{g}(x_{t})\;\middle|\;x_{t}\right]\in\partial f(x_{t})$
and $\partial f(x_{t})$ is the subgradient set of function $f$ at $x_{t}$.

  3. 3.

The subgradient estimate $\hat{g}(x_{t})$ is passed through a channel
$W_{t}\in\mathcal{W}$ and the output $Y_{t}$ is observed by the first-order
optimization algorithm. The algorithm then uses all the messages
$\\{Y_{i}\\}_{i\in[t]}$ to further update $x_{t}$ to $x_{t+1}$.

Let $\Pi_{T}$ be the set of all first-order optimization algorithms that are
allowed $T$ queries to the oracle $O$ and after the $t$th query gets back the
output $Y_{t}$ with distribution $W_{t}(\cdot\mid\hat{g}(x_{t}))$.

Our goal is to select gradient processing channels $W_{t}$s and an
optimization algorithm $\pi$ to guarantee a small worst-case optimization
error. Two classes of _channel selection strategies_ are of interest:
_adaptive_ and _nonadaptive_.

######  Definition 3.1.

Under adaptive gradient processing, the channel $W_{t}$ selected at time $t$
may depend on the previous outputs of channels $\\{W_{i}\\}_{i\in[t-1]}$.
Specifically, denoting by $Y_{t}$ the output of the channel used at time $t$,
which takes values in the output alphabet $\mathcal{Y}_{t}$, the _adaptive
channel selection strategy_ $S:=(S_{1},\ldots,S_{T})$ over $T$ iterations
consists of mappings $S_{t}\colon\mathcal{Y}^{t-1}\to\mathcal{W}$ that take
$Y_{1},\ldots Y_{t-1}$ as input and output a channel $W_{t}\in\mathcal{W}$ as
output. We write $\mathcal{S}_{\mathcal{W},T}$ for the collection of all such
channel selection strategies.

######  Definition 3.2.

Under nonadaptive gradient processing all the channels $\\{W_{t}\\}_{t\in[T]}$
through which the gradient estimates must pass are decided at the start of the
optimization algorithm. In other words, conditioned on the shared randomness,
the channel $W_{t}$ is selected independently of all the gradient observations
received by the optimization algorithm until step $t$. Denote the class of all
nonadaptive strategies by $\mathcal{S}_{\mathcal{W},T}^{\rm{}NA}$.

Figures 1(a), 1(b), and 1(c), describe the classical optimization framework,
information-constrained optimization under adaptive gradient processing, and
information-constrained optimization under nonadaptive gradient processing,
respectively.

We measure the performance of an optimization protocol $\pi$ and a channel
selection strategy $S$ for a given function $f$ and oracle $O$ using the
metric $\mathcal{E}(f,O,\pi,S)$ defined as

$\mathcal{E}(f,O,\pi,S)=\mathbb{E}\left[f(x_{T})-\min_{x\in\mathcal{X}}f(x)\right],$
(1)

where the expectation is over the randomness in $x_{T}$.

For various function and oracle classes, denoted by $\mathcal{O}$, the channel
constraint family $\mathcal{W}$, and the number of iterations $T$, we will
characterize the _adaptive minmax optimization error_

$\mathcal{E}^{\ast}(\mathcal{X},\mathcal{O},T,\mathcal{W})=\inf_{\pi\in\Pi_{T}}\inf_{S\in\mathcal{S}_{\mathcal{W},T}}\sup_{(f,O)\in\mathcal{O}}\mathcal{E}(f,O,\pi,S)\,,$
(2)

and the corresponding _nonadaptive minmax optimization error_

$\mathcal{E}^{\rm{}NA\ast}(\mathcal{X},\mathcal{O},T,\mathcal{W})=\inf_{\pi\in\Pi_{T}}\inf_{S\in\mathcal{S}_{\mathcal{W},T}^{\rm{}NA}}\sup_{(f,O)\in\mathcal{O}}\mathcal{E}(f,O,\pi,S)\,.$
(3)

Since the adaptive channel selection strategies include the nonadaptive ones,
we have
$\mathcal{E}^{\rm{}NA\ast}(\mathcal{X},\mathcal{O},T,\mathcal{W})\geq\mathcal{E}^{\ast}(\mathcal{X},\mathcal{O},T,\mathcal{W}).$

#####  2 Function classes

We now define the function classes and the corresponding oracles that we
consider.

###### Convex and $\ell_{p}$ Lipschitz function family.

Our first set of function families are parameterized by a number
$p\in[1,\infty]$. Throughout, we restrict ourselves to convex functions over a
domain $\mathcal{X}$, i.e., functions $f$ satisfying

$\displaystyle f(\lambda x+(1-\lambda)y)\leq\lambda
f(x)+(1-\lambda)f(y),\quad\forall
x,y\in\mathcal{X},\quad\forall\lambda\in[0,1].$ (4)

Further, for a family parameterized by $p$, we assume that the subgradient
estimates returned by the first-order oracle for a function $f$ satisfy the
following two assumptions:

$\displaystyle\mathbb{E}\left[\hat{g}(x)\mid x\right]\in\partial
f(x),\quad\text{(Unbiased estimates)}$ (5)
$\displaystyle\Pr\left(\|\hat{g}(x)\|_{q}^{2}\leq B^{2}\mid
x\right)=1,\quad\text{(Bounded estimates)}$ (6)

where $\partial f(x)$ is the set of subgradient for $f$ at $x$ and
$q:=p/(p-1)$ is, as mentioned earlier, the Hölder conjugate of $p$.

######  Definition 3.3 (Convex and $\ell_{p}$ Lipschitz function family
$\mathcal{O}_{{\tt c},p}$).

We denote by $\mathcal{O}_{{\tt c},p}$ the set of all pairs of functions and
oracles satisfying Assumptions (4), (5), and (6).

We note that (5) is standard in stochastic optimization literature ($cf.$
[71], [70], [15], [5]). To prove convergence guarantees on first-order
optimization in the classic setup (without any information constraints on the
oracle), it is enough to assume
$\displaystyle{\mathbb{E}\left[\|\hat{g}(x)\|_{q}^{2}\right]\leq B^{2}}$. We
make a slightly stronger assumption in this case since the more relaxed
assumption leads to technical difficulties in finding unbiased quantizers for
gradients.

Note that by (5) and (6) for every $x\in\mathcal{X}$ there exists a vector
$g\in\partial f(x)$ such that $\|g\|_{q}\leq B$. Further, since $f$ is convex,
$f(x)-f(y)\leq g^{T}(x-y)$ for every $g\in\partial f(x)$, whereby
$|f(x)-f(y)|\leq B\|x-y\|_{p}$. Namely, $f$ is $B$-Lipschitz continuous in the
$\ell_{p}$ norm.222The same could be said under the weaker assumption
$\mathbb{E}\left[\|\hat{g}(x)\|_{q}^{2}\right]\leq B^{2}$.

Before proceeding, we recall the optimal convergence results under no
information constraints. No information constraints can be viewed as passing
the subgradients estimates through the identity channel.

######  Definition 3.4.

We denote by $I:\mathbb{R}^{d}\to\mathbb{R}^{d}$ the identity channel, where
the output always equals the input. Let $\mathcal{I}$ denote the singleton set
consisting only of $I$.

######  Theorem 3.5.

Let
$\mathbb{X}_{p}(D):=\\{\mathcal{X}\subseteq\mathbb{R}^{d}:\max_{x,y\in\mathcal{X}}\|x-y\|_{p}\leq
D\\}.$ There exist absolute constants $c_{0}$ and $c_{1}$ where $c_{1}\geq
c_{0}>0$ such that the following hold:

  1. 1.

for333For certain range of $p$ closer to 2 the $\sqrt{\log d}$ factor can be
removed; for simplicity, we state the slightly weaker result. $2>p\geq 1$,

$\displaystyle{\frac{c_{1}DB\sqrt{\log
d}}{\sqrt{T}}\geq\sup_{\mathcal{X}\in\mathbb{X}_{p}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
c},p},T,\mathcal{I})\geq\frac{c_{0}DB}{\sqrt{T}}.}$

  2. 2.

For $p\geq 2$,

$\displaystyle{\frac{c_{1}d^{1/2-1/p}DB}{\sqrt{T}}\geq\sup_{\mathcal{X}\in\mathbb{X}_{p}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
c},p},T,\mathcal{I})\geq\frac{c_{0}d^{1/2-1/p}DB}{\sqrt{T}};}$

The lower bounds and the upper bounds can be found, for instance, in [5,
Theorem 1] and [5, Appendix C].

######  Remark 1.

An optimal achievable scheme for $p\in[1,2)$ is the stochastic mirror descent
with the mirror maps $\|x\|_{p^{\prime}}^{2}/(p^{\prime}-1)$, where
$p^{\prime}$ is chosen appropriately for a given $p$. When Hölder conjugate
$q$ of $p$ is $o(\log d)$, we choose $p^{\prime}$ to be $p$. When $q$ is
$\Omega(\log d)$, we choose $p^{\prime}=\frac{2\log d}{2\log d-1}.$ Further,
these algorithms require only that the expected squared $\ell_{q}$ norm of the
gradient estimates are bounded.

######  Remark 2.

An optimal achievable scheme for $p$ greater than $2$ is simply projected
subgradient descent(PSGD). To see this, note that PSGD gives a guarantee of
${D^{\prime}B^{\prime}}/{\sqrt{T}}$ ($cf.$ [70]), where $D^{\prime}$ is the
$\ell_{2}$ diameter and $B^{\prime}$ is the bound on
$\mathbb{E}\left[\|\hat{g}\|_{2}^{2}\right]$. Using the monotonicity of
$\ell_{q}$ norms in $q$, for $q\geq 2$ we have
$\mathbb{E}\left[\|\hat{g}\|_{2}^{2}\right]\leq\mathbb{E}\left[\|\hat{g}\|_{q}^{2}\right]\leq
B^{2}$. Also, the $\ell_{2}$ diameter of a unit $\ell_{p}$ ball is
$d^{1/2-1/p}$. It follows that PSGD attains the upper bounds in Theorem 3.5.

###### Strongly convex and $\ell_{2}$ Lipschitz function family.

We now consider a special subset of the convex and $\ell_{2}$ Lipschitz family
described above, where the functions are strongly convex. Recall that for
$\gamma>0$, a function $f$ is _$\gamma$ -strongly convex on $\mathcal{X}$_ if
the following function $h$ is convex:

$\displaystyle h(x)=f(x)-\frac{\gamma}{2}\|x\|_{2}^{2},\quad\forall
x\in\mathcal{X}.$ (7)

######  Definition 3.6 (Strongly convex and $\ell_{2}$ Lipschitz function
family $\mathcal{O}_{{\tt sc}}$.).

We denote by $\mathcal{O}_{{\tt sc}}$ the set of all pairs of functions and
oracles satisfying (4), (5), (7), and (6) for $q=2$.

The strong convexity parameter $\gamma$ is related to the parameter $B$, the
upper bound on the $\ell_{2}$ norm of the gradient estimate. We state a
relation between them when the domain $\mathcal{X}$ contains an
$\ell_{\infty}$ ball of radius $D$ centered at the origin; this property will
be used when we derive lower bounds.

######  Lemma 3.7.

For any $\mathcal{X}\supseteq\\{x:\|x\|_{\infty}\leq D\\}$, we have
$\frac{B}{\gamma}\geq\frac{Dd^{1/2}}{4}.$

######  Theorem 3.8.

Let
$\mathbb{X}_{2}(D):=\\{\mathcal{X}\subseteq\mathbb{R}^{d}:\max_{x,y\in\mathcal{X}}\|x-y\|_{2}\leq
D\\}.$ There exist absolute constants $c_{0}$ and $c_{1}$ where $c_{1}\geq
c_{0}>0$ such that the following hold:

$\frac{c_{1}B^{2}}{\gamma
T}\geq\sup_{\mathcal{X}\in\mathbb{X}_{2}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{\tt
sc},T,\mathcal{I})\geq\frac{c_{0}B^{2}}{\gamma T}$

The lower bounds and the upper bounds can be found, for instance, in [5,
Theorem 1] and [70].

######  Remark 3.

The optimal achievable scheme for strongly convex functions is the stochastic
gradient descent algorithm.

#####  3 Information constraints

We describe three specific constraints of interest to us: local privacy,
communication, and computation. The first two are well-studied; the third is
new and arises in procedures such as random coordinate descent.

###### Local differential privacy.

To model local privacy, we define the $\varepsilon$-locally differentially
private (LDP) channel family $\mathcal{W}_{{\tt priv},\varepsilon}$.

######  Definition 3.9.

A channel $W\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ is _$\varepsilon$ -locally
differentially private_ ($\varepsilon$-LDP) if for all
$x,x^{\prime}\in\mathbb{R}^{d}$,

$\frac{W(Y\in S\mid X=x)}{W(Y\in S\mid X=x^{\prime})}\leq e^{\varepsilon}$

for all Borel measurable subsets $S$ of $\mathbb{R}^{d}$. We denote by
$\mathcal{W}_{{\tt priv},\varepsilon}$ the set of all $\varepsilon$-LDP
channels.

When operating under local privacy constraints, the oracle’s subgradient
estimates are passed through an $\varepsilon$-LDP channel, and only the output
is available to the optimization algorithm. Thus, the resulting process which
handles the data of individual users, accessed in each oracle query, is
overall differentially private, a notion of privacy extensively studied and
widely used in practice.

###### Communication constraints.

To model communication constraints, we define the $\mathcal{W}_{{\tt com},r}$,
the $r$-bit communication-constrained channel family, as follows.

######  Definition 3.10.

A channel $W\colon\mathbb{R}^{d}\to\\{0,1\\}^{r}$ constitutes an _$r$ -bit
communication-constrained_ channel. We denote by $\mathcal{W}_{{\tt com},r}$
the set of all $r$-bit communication-constrained channels.

###### Computational constraints.

For high-dimensional optimization, altogether computing the subgradient
estimates can be computationally expensive. Often in such cases, one resorts
to computing only a few coordinates of the gradient estimates and using only
them for optimization ([73, 80]). This motivates the oblivious sampling
channel family $\mathcal{W}_{\tt obl}$, where the optimization algorithm gets
to see only one randomly chosen coordinate of the gradient estimate.

######  Definition 3.11.

An _oblivious sampling_ channel $W$ is a channel
$W\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ specified by a probability vector
$(p_{i})_{i\in[d]}$, $i.e.$, a vector $p$ such that $p_{i}\geq 0$ for all $i$
and $\sum_{i\in[d]}p_{i}=1$. For an input $g\in\mathbb{R}^{d}$, the output
distribution of $W$ is given by $W(g(i)e_{i}\mid g)=p_{i},\forall i\in[d]$. We
denote by $\mathcal{W}_{\tt obl}$ the set of all oblivious sampling channels.

Therefore, at most one coordinate of the oracle’s the gradient estimate can be
used by the optimization algorithm. Further, this coordinate is sampled
obliviously to the input gradient estimate itself.

######  Remark 4.

We note that the special case of $p_{i}=\frac{1}{d}$ $\forall\,i\in[d]$
corresponds to sampling employed by standard _Random Coordinate Descent_ (RCD)
($cf$. [15, Section 6.4]), where at each time step only one uniformly random
coordinate of the gradient is used by the gradient descent algorithm.

####  4 Main results: lower bounds for information-constrained optimization

For $p\in[1,\infty]$ and $D>0$, let
$\mathbb{X}_{p}(D):=\\{\mathcal{X}\subseteq\mathbb{R}^{d}:\max_{x,y\in\mathcal{X}}\|x-y\|_{p}\leq
D\\}$ be the collection of subsets of $\mathbb{R}^{d}$ whose $\ell_{p}$
diameter is at most $D$. In stating our results, we will fix throughout the
parameter $B>0$, the almost sure bound on the gradient magnitude defined in
(6), as well as the strong convexity parameter $\gamma>0$ defined in (7)
(which, implicitly, is required to satisfy Lemma 3.7). Throughout this
section, our lower bounds on minmax optimization error focus on tracking the
convergence rate for large $T$, a standard regime of interest for the
stochastic optimization setting.

#####  1 Lower bounds for locally private optimization under adaptive gradient
processing

Throughout, we consider $\varepsilon\in[0,1]$, namely the high-privacy regime.

###### Convex function family.

For the convex function family, we prove the following lower bounds.

######  Theorem 4.1.

Let $p\in[1,2]$, $\varepsilon\in[0,1]$, and $D>0$. There exist absolute
constants $c_{0},c_{1}>0$ such that, for $T\geq
c_{0}\frac{d}{\varepsilon^{2}}$,

$\sup_{\mathcal{X}\in\mathbb{X}_{p}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
c},p},T,\mathcal{W}_{{\tt
priv},\varepsilon})\geq\frac{c_{1}DB}{\sqrt{T}}\cdot\sqrt{\frac{d}{\varepsilon^{2}}}.$

(Moreover, one can take $c_{0}:=\frac{1}{2e(e-1)^{2}}$ and
$c_{1}:=\frac{1}{36(e-1)\sqrt{2e}}$.)

See Section 5 for the proof.

######  Theorem 4.2.

Let $p\in(2,\infty],\varepsilon\in[0,1]$, and $D>0$. There exist absolute
constants $c_{0},c_{1}>0$ such that, for $T\geq
c_{0}\frac{d^{2}}{\varepsilon^{2}}$,

$\sup_{\mathcal{X}\in\mathbb{X}_{p}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
c},p},T,\mathcal{W}_{{\tt
priv},\varepsilon})\geq\frac{c_{1}DBd^{1/2-1/p}}{\sqrt{T}}\cdot\sqrt{\frac{d}{\varepsilon^{2}}}.$

(Moreover, one can take $c_{0}$ and $c_{1}$ as in Theorem 4.1.)

See Section 6 for the proof.

######  Remark 5 (Tightness of bounds for convex functions and LDP
constraints).

[24, Theorem 4 and 5] provide nonadaptive LDP algorithms which show that
Theorem 4.1 is tight up to logarithmic factors for $p=1$ and Theorem 4.2 is
tight up to constant factors for all $p\in(2,\infty]$ (to the best of our
knowledge, no non-trivial upper bound is known for $p\in(1,2)$.). Therefore,
adaptive processing of gradients under LDP cannot significantly improve the
convergence rate for convex function families.

Interestingly, for $p=1,$ [24] also provide a slightly stronger lower bound of
$\frac{c_{0}DB}{\sqrt{T}}\cdot\sqrt{\frac{d\log d}{\varepsilon^{2}}}$ for
nonadaptive protocols, which matches the performance of their nonadaptive
protocols up to constant factors. This points to a minor gap in our
understanding of adaptive protocols: Can we establish a stronger lower bound
for adaptive protocols to match the performance of the nonadaptive algorithm
of [24], or does there exist a better adaptive protocol?

From Theorem 3.5, the standard optimization error for $\ell_{p}$,
$p\in[1,\infty]$, convex family blows up by a factor of
$\sqrt{d/\varepsilon^{2}}$ when the gradient estimates are passed through an
$\varepsilon$-LDP channel.

###### Strongly convex family.

We prove the following result for strongly convex functions.

######  Theorem 4.3.

Let $\varepsilon\in[0,1]$, and $D>0$. There exist absolute constants
$c_{0},c_{1}>0$ such that, for $T\geq
c_{0}\cdot\frac{B^{2}}{\gamma^{2}D^{2}}\cdot\frac{d}{\varepsilon^{2}}$,

$\sup_{\mathcal{X}\in\mathbb{X}_{2}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
sc}},T,\mathcal{W}_{{\tt priv},\varepsilon})\geq\frac{c_{1}B^{2}}{\gamma
T}\cdot\frac{d}{\varepsilon^{2}}.$

See Section 7 for the proof.

######  Remark 6 (Tightness of bounds for strongly convex functions and LDP
constraints).

One can use stochastic gradient descent with the nonadaptive protocol from
[24, Appendix C.2] to obtain a nonadaptive protocol with convergence rate
matching the lower bound in Theorem 4.3 up to constant factors, establishing
that adaptivity does not help for strongly convex functions.

From Theorem 3.8, the standard optimization error for strongly convex
functions blows up by a factor of $\frac{d}{\varepsilon^{2}}$ when the
gradient estimates are passed through an $\varepsilon$-LDP channel.

#####  2 Lower bounds on communication-constrained optimization

Convex function family. For convex functions, we prove the following lower
bounds.

######  Theorem 4.4.

Let $p\in[1,2]$, and $D>0$. There exists an absolute constant $c_{0}>0$ such
that, for $r\in\mathbb{N}$, and $T\geq\frac{d}{6r},$

$\sup_{\mathcal{X}\in\mathbb{X}_{p}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
c},p},T,\mathcal{W}_{{\tt
com},r})\geq\frac{c_{0}DB}{\sqrt{T}}\cdot\sqrt{\frac{d}{d\wedge r}}.$

(Moreover, one can take $c_{0}:=\frac{1}{12\sqrt{58}}$.)

See Section 7 for the proof.

######  Theorem 4.5.

Let $p\in(2,\infty]$, and $D>0$. There exists an absolute constant $c_{0}>0$
such that, for $r\in\mathbb{N}$, and
$T\geq\frac{1}{{{4}}}\cdot\frac{d^{2}}{2^{r}\land d}$, we have

$\sup_{\mathcal{X}\in\mathbb{X}_{p}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
c},p},T,\mathcal{W}_{{\tt
com},r})\geq\left(\frac{c_{0}DBd^{1/2-1/p}}{\sqrt{T}}\cdot\sqrt{\frac{d}{d\wedge
2^{r}}}\right)\vee\left(\frac{c_{0}DB}{\sqrt{T}}\cdot\sqrt{\frac{d}{d\wedge
r}}\right)$

(Moreover, one can take $c_{0}:=\frac{1}{12\sqrt{58}}$.)

See Section 6 for the proof.

In Chapters 2 and 3, we will derive upper bounds for most regimes of $p$ and
$r.$ Specifically, restricting $r\geq r^{*}(T,p)$ our bounds are tight for all
regimes of $p$. Moreover, for $p=1$ and $[2,\infty]$, our bounds are nearly
tight for all $r$.

From Theorem 3.5, the standard optimization errors for $\ell_{1}$ and
$\ell_{p}$, $p\in(2,\infty]$, convex family blow up by a factor of
$\sqrt{\frac{d}{d\wedge r}}$ and $\sqrt{\frac{d}{d\wedge
2^{r}}}\vee\sqrt{\frac{d^{2/p}}{d\wedge r}}$, respectively, when the gradient
estimates are compressed to $r$ bits.

###### Strongly convex family.

We prove the following result for strongly convex functions.

######  Theorem 4.6.

Let $D>0$. There exist absolute constants $c_{0},c_{1}>0$ such that, for
$r\in\mathbb{N}$ and $T\geq
c_{0}\cdot\frac{B^{2}}{\gamma^{2}D^{2}}\cdot\frac{d}{r}$,

$\sup_{\mathcal{X}\in\mathbb{X}_{2}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
sc}},T,\mathcal{W}_{{\tt com},r})\geq\frac{c_{1}B^{2}}{\gamma
T}\cdot\frac{d}{d\land r}\,.$

See Section 7 for the proof.

In Chapters 2, we will derive upper bounds which are tight upto a factor of
$\log\log^{*}d$ for all $r.$ From Remark 3, the standard optimization error
for strongly convex functions blows up by a factor of $\frac{d}{r}$ when the
gradient estimates are compressed to $r$ bits.

#####  3 Lower bounds on computationally-constrained optimization

We restrict to the case of Euclidean geometry ($p=2$) for the oblivious
sampling channel family $\mathcal{W}_{\tt obl}$. Our motivation for
introducing this class was to study the optimality of standard RCD, which is
proposed to work in the Euclidean setting alone. Furthermore, if we consider a
slightly larger family of channels where the sampling probabilities can depend
on the input itself, the resulting family will be similar to the 1-bit
communication family, which we have addressed in Section 2.

###### Convex family.

For convex functions, we establish the following lower bound, for $p=2$.

######  Theorem 4.7.

Let $D>0$. There exists an absolute constant $c_{0}>0$ such that, for
$T\geq\frac{d}{4}$, we have

$\sup_{\mathcal{X}\in\mathbb{X}_{2}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
c},2},T,\mathcal{W}_{{\tt obl}})\geq\frac{c_{0}\sqrt{d}DB}{\sqrt{T}}\,.$

(Moreover, one can take $c_{0}:=\frac{1}{72}$.)

See Section 5 for a proof.

The standard Random Coordinate Descent (RCD) (see for instance [15, Theorem
6.6]), which employs uniform sampling, matches this lower bound up to constant
factors. The optimality of standard RCD motivates further the folklore
approach of uniformly sampling coordinates for random coordinate descent
unless there is an obvious structure to exploit (as in [72]). This establishes
that adaptive sampling strategies do not improve over nonadaptive sampling
strategies for the family $\mathcal{W}_{{\tt obl}}$. Also from Theorem 3.5,
the standard optimization error for $\ell_{2}$ convex family blows up by a
factor of $\sqrt{d}$ when the gradient coordinates are sampled obliviously.

###### Strongly convex family.

For strongly convex functions, we obtain the following lower bound, for $p=2$.

######  Theorem 4.8.

Let $D>0$. There exist absolute constants $c_{0},c_{1}>0$ such that, for
$T\geq c_{0}\cdot d\frac{B^{2}}{\gamma^{2}D^{2}}$, we have

$\sup_{\mathcal{X}\in\mathbb{X}_{2}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
sc}},T,\mathcal{W}_{{\tt obl}})\geq\frac{c_{1}dB^{2}}{\gamma T}\,.$

See Section 7 for the proof.

Once again, the standard RCD algorithm matches this lower bound, which shows
that adaptive sampling strategies do not improve over nonadaptive sampling
strategies for strongly convex optimization. Further, from Theorem 3.8, the
standard optimization error for strongly convex family blows up by a factor of
$d$ when the gradient coordinates are sampled obliviously.

| LDP | Communication | Computational
---|---|---|---
| constraints | -constraints | -constraints
Convex and $\ell_{p}$ |  |  | (Only for $p=2$)
Lipschitz function | $\displaystyle{\frac{c_{1}DB}{\sqrt{T}}\cdot\sqrt{\frac{d}{\varepsilon^{2}}}}$ | $\displaystyle{\frac{c_{1}DB}{\sqrt{T}}\cdot\sqrt{\frac{d}{d\land r}}}$ | $\displaystyle{\frac{c_{1}DB}{\sqrt{T}}\cdot\sqrt{d}}$
family ($p\in[1,2]$) | (Theorem 4.1) | (Theorem 4.4) | (Theorem 4.7)
Convex and $\ell_{p}$ |  | $\left(\frac{c_{0}DBd^{1/2-1/p}}{\sqrt{T}}\cdot\sqrt{\frac{d}{d\wedge 2^{r}}}\right)$ |
Lipschitz function | $\displaystyle{\frac{c_{1}DBd^{1/2-1/p}}{\sqrt{T}}\cdot\sqrt{\frac{d}{\varepsilon^{2}}}}$ | $\vee\left(\frac{c_{0}DB}{\sqrt{T}}\cdot\sqrt{\frac{d}{d\wedge r}}\right)$ | N.A.
family ($p\in(2,\infty]$) | (Theorem 4.2) | (Theorem 4.5) |
Strongly convex and $\ell_{2}$ |  |  |
Lipschitz function | $\displaystyle{\frac{c_{1}B^{2}}{\gamma T}\cdot\frac{d}{\varepsilon^{2}}}$ | $\displaystyle{\frac{c_{1}B^{2}}{\gamma T}\cdot\frac{d}{r}}$ | $\displaystyle{\frac{c_{1}dB^{2}}{\gamma T}}$
family | (Theorem 4.3) | (Theorem 4.6) | (Theorem 4.8)
Table 2: Summary of all our lower bounds on gap-to-optimality for information-
constrained optimization.

A summary of all our lower bounds is provided in Table 2.

####  5 Proofs of lower bounds

#####  1 Outline of the proof for our lower bounds

The proofs of our lower bounds for adaptive protocols follow the same general
template, summarized below.

Step 1. Relating optimality gap to average information: We consider a family
of functions $\mathcal{G}=\\{g_{v}:v\in\\{-1,1\\}^{d}\\}$ satisfying suitable
conditions and associate with it a “discrepancy metric” $\psi(\mathcal{G})$
that allows us to relate the optimality gap of any algorithm to an average
mutual information quantity. Specifically, for $V$ distributed uniformly over
$\\{-1,1\\}^{d}$, we show that the output $\hat{x}$ of any optimization
algorithm satisfies

$\mathbb{E}\left[g_{V}(\hat{x})-\min_{x\in\mathcal{X}}g_{V}(x)\right]\geq{\frac{d\psi(\mathcal{G})}{6}}\left[1-\sqrt{\frac{{{2}}}{d}\sum_{i=1}^{d}I\left(V(i)\land
Y^{T}\right)}\right],$

where $Y_{t}$ is the channel output for the gradient in the $t$th iteration
and $Y^{T}:=(Y_{1},\dots,Y_{T})$.

Heuristically, we have related the gap to optimality to the difficulty of
inferring $V$ by observing $Y^{T}$. We note that the bound above is similar to
that of [5], but instead of mutual information $I\left(V\land Y^{T}\right)$ we
get the average mutual information per coordinate. This latter quantity is
amenable to analysis for adaptive protocols.

Step 2. Average information bounds: To bound the average mutual information
per coordinate, $\frac{1}{d}\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)$, we
take recourse to the recently proposed bounds from [3]. These bounds hold for
$Y^{T}$ which is the output of adaptively selected channels from a fixed
channel family $\mathcal{W}$, with i.i.d. input $X^{T}=(X_{1},\dots,X_{T})$
generated from a family of distributions
$\\{\mathbf{p}_{v},v\in\\{-1,1\\}^{d}\\}$. We view the output of oracle as
inputs $X^{T}$ and derive the required bound.

While results in [3] provided bounds for $\mathcal{W}_{{\tt
priv},\varepsilon}$ and $\mathcal{W}_{{\tt comm},r}$, we extend the approach
to handle $\mathcal{W}_{{\tt obl}}$. Specifically, under a smoothness and
symmetry condition on $\\{\mathbf{p}_{v},v\in\\{-1,1\\}^{d}\\}$, which has a
parameter $\gamma$ associated with it, we show the following:

For $|\mathcal{X}|<\infty$ and $\mathcal{X}_{i}:=\\{x(i):x\in\mathcal{X}\\}$,
$i\in[d]$, we have

$\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)\leq\frac{C}{2}\cdot T\gamma^{2},$

where the constant $C$ depends only on
$\\{\mathbf{p}_{v},v\in\\{-1,+1\\}^{d}\\}$ and, denoting by $v^{\oplus
i}\in\\{-1,1\\}^{d}$ the vector with the sign of the $i$th coordinate of $v$
flipped, is given by

$C=(\max_{i\in[d]}|\mathcal{X}_{i}|-1)\cdot\max_{x\in\mathcal{X}}\max_{v\in\\{-1,+1\\}^{d}}\max_{i\in[d]}\frac{\mathbf{p}_{v^{\oplus
i}}(X(i)=x(i))}{\mathbf{p}_{v}(X(i)=x(i))}.$

Step 3. Use appropriate difficult instances On the one hand, to prove lower
bounds for the convex family we will use the class of functions
$\mathcal{G_{\tt c}}=\\{g_{v}(x)\colon v\in\\{-1,1\\}^{d}\\}$ defined on the
domain $\mathcal{X}=\\{x\in\mathbb{R}^{d}:\|x\|_{\infty}\leq b\\}$ comprising
functions $g_{v}$ given below:

$\displaystyle g_{v}(x)=a\cdot\sum_{i=1}^{d}|x(i)-v(i)\cdot b|,\quad\forall
x\in\mathcal{X},v\in\\{-1,1\\}^{d}.$

On the other hand, to prove lower bounds for the strongly convex family, we
will use the class of functions $\mathcal{G_{\tt sc}}=\\{g_{v}(x)\colon
v\in\\{-1,1\\}^{d}\\}$ on
$\mathcal{X}=\\{x\in\mathbb{R}^{d}:\|x\|_{\infty}\leq b\\}$ given by

$\displaystyle g_{v}(x)=a\sum_{i=1}^{d}\left(\frac{1+2\delta
v(i)}{2}f^{+}_{i}(x)+\frac{1-2\delta v(i)}{2}f^{-}_{i}(x)\right),\quad\forall
x\in\mathcal{X},v\in\\{-1,1\\}^{d},$

where $f^{+}_{i}$ and $f^{-}_{i}$, for $i\in[d]$, are given by

$\displaystyle f^{+}_{i}(x)=\theta
b|x(i)+b|+\frac{1-\theta}{4}(x(i)+b)^{2},\qquad f^{-}_{i}(x)$
$\displaystyle=\theta b|x(i)-b|+\frac{1-\theta}{4}(x(i)-b)^{2}.$

Step 4. Carefully combine everything: We obtain our desired bounds by applying
Steps 1 and 2 to difficult instances from Step 3. Since the difficult instance
for convex family consists of linear functions, the gradient does not depend
on $x$. Thus, we can design oracles which give i.i.d. output with distribution
independent of the query point $x_{t}$, whereby the bound in Step 2 can be
applied. Interestingly, we construct different oracles for $p<2$ and $p\geq
2$.

However, the situation is different for the strongly convex family. The
gradients now depend on the query point $x_{t}$, whereby it is unclear if we
can comply with the requirements in Step 2. Interestingly, for communication
and local privacy constraints, we construct oracles that allow us to view
messages $Y^{T}$ as the output of adaptively selected channels applied to
independent samples from a common distribution $\mathbf{p}_{v}$. While it is
unclear if the same can be done for computational constraints as well, we use
an alternative approach and exhibit an oracle for which we can find an
intermediate message vector $Z_{1},\dots,Z_{T}$ such that (i) $V$ and $Y^{T}$
are conditionally independent given $Z^{T}$ and (ii) the message $Z^{T}$
satisfies the requirements of Step 2.

#####  2 Relating optimality gap to average information

In this section, we prove a general lower bound for the expected gap to
optimality by considering a parameterized family of functions and oracles
which is contained in our oracle family of interest. We present a bound that
relates the expected gap to optimality to the average mutual information
between the channel output and different coordinates of the unknown parameter.
This step is the key difference between our approach and that of [5], which
used Fano’s method instead of our bound below. We remark that the bounds
resulting from Fano’s method are typically not amenable to analysis for
adaptive protocols.

In more detail, our result can be used to prove bounds for the average
optimization error over any class of functions which satisfies the two
conditions below.

######  Assumptions 5.1.

Let $\mathcal{X}\subseteq\mathbb{R}^{d}$ and $\mathcal{V}=\\{-1,1\\}^{d}$. Let
$\mathcal{G}=\\{g_{v}:v\in\mathcal{V}\\}$ where
$g_{v}:\mathcal{X}\to\mathbb{R}$ are real-valued functions from $\mathcal{X}$
such that

  1. 1.

the $g_{v}$s are _coordinate-wise decomposable_ , $i.e.$, there exist
functions $g_{i,b}\colon\mathbb{R}\to\mathbb{R}$, $i\in[d]$, $b\in\\{-1,1\\}$,
such that

$g_{v}(x)=\sum_{i=1}^{d}g_{i,v(i)}(x(i)).$

  2. 2.

the minimum of $g_{v}$ is also a _coordinate-wise minimum_ , $i.e.$, if we
denote by $x^{\ast}_{v}$ the minimum of $g_{v}$ over $\mathcal{X}$, then, for
all $i\in[d]$, we have

$x^{\ast}_{v}(i)=\arg\\!\min_{y\in\mathcal{X}_{i}}g_{i,v(i)}(y),$

where $\mathcal{X}_{i}=\\{x(i):x\in\mathcal{X}\\}$.

For $\mathcal{G}$ satisfying Assumptions 5.1 and for $i\in[d]$, we now define
the following discrepancy metric:

$\displaystyle\psi_{i}(\mathcal{G})$
$\displaystyle:=\min_{y\in\mathcal{X}_{i}}\left(g_{i,1}(y)+g_{i,-1}(y)-\left(\min_{y^{\prime}\in\mathcal{X}_{i}}g_{i,1}(y^{\prime})+\min_{y^{\prime}\in\mathcal{X}_{i}}g_{i,-1}(y^{\prime})\right)\right)$
(8) $\displaystyle\psi(\mathcal{G})$
$\displaystyle:=\min_{i\in[d]}\psi_{i}(\mathcal{G}).$ (9)

This is a “coordinate-wise counterpart” of the metric used in [5]. The next
lemma follows readily from this definition.

######  Lemma 5.2.

Fix $i\in[d]$. For every $y\in\mathcal{X}_{i}$, there can be at most one
$b\in\\{-1,1\\}$ such that

$g_{i,b}(y)-\min_{y^{\prime}\in\mathcal{X}_{i}}g_{i,b}(y^{\prime})\leq\frac{\psi_{i}(\mathcal{G})}{3}.$

###### Proof.

Let $b\in\\{-1,1\\}$. By definition of $\psi_{i}(\mathcal{G})$, for all
$y\in\mathcal{X}_{i}$ we have

$\left(g_{i,b}(y)-\min_{y^{\prime}\in\mathcal{X}_{i}}g_{i,b}(y^{\prime})\right)+\left(g_{i,-b}(y)-\min_{y^{\prime}\in\mathcal{X}_{i}}g_{i,-b}(y^{\prime})\right)\geq\psi_{i}(\mathcal{G}).$

For $y$ such that
$g_{i,b}(y)-\min_{y^{\prime}\in\mathcal{X}_{i}}g_{i,b}(y^{\prime})\leq\frac{\psi_{i}(\mathcal{G})}{3}$,
we now must have that

$g_{i,-b}(y)-\min_{y^{\prime}\in\mathcal{X}_{i}}g_{i,-b}(y^{\prime})\geq\frac{2\psi_{i}(\mathcal{G})}{3}.\qed$

We will use this observation to bound the expected gap to optimality for any
algorithm $\pi$ optimizing an unknown function in $\mathcal{G}$ that has
access to only the corresponding first-order oracle.

######  Lemma 5.3.

Suppose $\mathcal{G}=\\{g_{v}:v\in\\{-1,1\\}^{d}\\}$ satisfies Assumption 5.1.
Let $\pi$ be any optimization algorithm that adaptively selects the channels
$\\{W_{j}\\}_{j\in[T]}$. For a random variable $V$ distributed uniformly over
$\\{-1,1\\}^{d}$, the output $\hat{x}$ of $\pi$ when it is applied to a
function from $\mathcal{G}$ and any associated (stochastic subgradient) oracle
satisfies

$\mathbb{E}\left[g_{V}(\hat{x})-g_{V}(x_{V}^{\ast})\right]\geq{\frac{d\psi(\mathcal{G})}{6}}\left[1-\sqrt{\frac{1}{d}\sum_{i=1}^{d}{{2}}I\left(V(i)\land
Y^{T}\right)}\right],$

where $\psi(\mathcal{G})=\min_{j\in[d]}\psi_{j}(\mathcal{G})$, $Y_{t}$ is the
channel output for the gradient at time step $t$ and
$Y^{T}:=(Y_{1},\dots,Y_{T})$.

###### Proof.

Our proof is based on relating the gap to optimality to the error in
estimation of $V$ upon observing $Y^{T}$. Suppose the algorithm $\pi$ along
with channels $\\{W_{j}\\}_{j\in[T]}$ outputs the point $\hat{x}$ after $T$
iterations. By linearity of expectation, the decomposability of $g_{v}$, and
Markov’s inequality, we have

$\displaystyle\mathbb{E}\left[g_{V}(\hat{x})-g_{V}(x_{V}^{\ast})\right]$
$\displaystyle=\sum_{i=1}^{d}\mathbb{E}\left[g_{i,V(i)}(\hat{x}(i))-g_{i,V(i)}(x_{V}^{\ast}(i))\right]$
$\displaystyle\geq\sum_{i=1}^{d}\frac{\psi_{i}(\mathcal{G})}{3}\Pr\left(g_{i,V(i)}(\hat{x}(i))-g_{i,V(i)}(x_{V}^{\ast}(i))\geq\frac{\psi_{i}(\mathcal{G})}{3}\right)$
$\displaystyle\geq\frac{\psi(\mathcal{G})}{3}\sum_{i=1}^{d}\Pr\left(g_{i,V(i)}(\hat{x}(i))-g_{i,V(i)}(x_{V}^{\ast}(i))\geq\frac{\psi_{i}(\mathcal{G})}{3}\right).$
(10)

We proceed to bound each summand separately.

Fix any $i\in[d]$ and consider the following estimate for $V(i)$: Given
$\hat{x}$, we output a $\hat{V}(i)\in\\{-1,1\\}$ satisfying

$g_{i,\hat{V}(i)}(\hat{x}(i))-{{\min_{y^{\prime}\in\mathcal{X}_{i}}g_{i,\hat{V}(i)}(y^{\prime})}}<\frac{\psi_{i}(G)}{3};$

if no such $\hat{V}(i)$ exists, we generate $\hat{V}(i)$ uniformly from
$\\{-1,1\\}$. Then, as a consequence of Lemma 5.2, we get

$\Pr\left(\hat{V}(i)\neq
v(i)\right)\leq\Pr\left(g_{i,v(i)}(\hat{x}(i))-g_{i,v(i)}(x_{v}^{\ast}(i))\geq\frac{\psi_{i}(\mathcal{G})}{3}\right).$
(11)

Next, denote by $\mathbf{p}^{Y^{T}}$ the distribution of $Y^{T}$ and by
$\mathbf{p}_{+i}^{Y^{T}}$ and $\mathbf{p}_{-i}^{Y^{T}}$, respectively, the
distributions of $Y^{T}$ given $V(i)=+1$ and $V(i)=-1$. It is easy to verify
that

$\mathbf{p}^{Y^{T}}=\frac{1}{2}(\mathbf{p}_{+i}^{Y^{T}}+\mathbf{p}_{-i}^{Y^{T}}),\quad\forall\,i\in[d].$

Noting that $V(i)$ is uniform and the estimate $\hat{V}(i)$ is formed as a
function of $Y^{T}$, we get

$\Pr\left(\hat{V}(i)\neq
v(i)\right)\geq\frac{1}{2}-\frac{1}{2}{\operatorname{d}_{\rm
TV}\left({\mathbf{p}_{+i}^{Y^{T}},\mathbf{p}_{-i}^{Y^{T}}}\right)}.$ (12)

From this, combining (11) and (12) and plugging the result into (10), we have

$\displaystyle\mathbb{E}\left[g_{v}(\hat{x})-g_{v}(x_{v}^{\ast})\right]$
$\displaystyle\geq\frac{\psi(\mathcal{G})}{6}\sum_{i=1}^{d}\left[1-{\operatorname{d}_{\rm
TV}\left({\mathbf{p}_{+i}^{Y^{T}},\mathbf{p}_{-i}^{Y^{T}}}\right)}\right]$
$\displaystyle\geq\frac{\psi(\mathcal{G})}{6}\sum_{i=1}^{d}\left[1-{\operatorname{d}_{\rm
TV}\left({\mathbf{p}_{+i}^{Y^{T}},\mathbf{p}^{Y^{T}}}\right)}-{\operatorname{d}_{\rm
TV}\left({\mathbf{p}_{-i}^{Y^{T}},\mathbf{p}^{Y^{T}}}\right)}\right]$
$\displaystyle\geq\frac{\psi(\mathcal{G})}{6}\sum_{i=1}^{d}\left[1-\sqrt{\frac{1}{2}{\operatorname{D}\left({\mathbf{p}_{+i}^{Y^{T}}\|\mathbf{p}^{Y^{T}}}\right)}}-\sqrt{\frac{1}{2}{\operatorname{D}\left({\mathbf{p}_{-i}^{Y^{T}}\|\mathbf{p}^{Y^{T}}}\right)}|}\right]$
$\displaystyle\geq\frac{d\psi(\mathcal{G})}{6}\left[1-\sqrt{\frac{1}{d}\sum_{i=1}^{d}{\operatorname{D}\left({\mathbf{p}_{+i}^{Y^{T}}\|\mathbf{p}^{Y^{T}}}\right)}+{\operatorname{D}\left({\mathbf{p}_{-i}^{Y^{T}}\|\mathbf{p}^{Y^{T}}}\right)}}\right]$
$\displaystyle=\frac{d\psi(\mathcal{G})}{6}\left[1-\sqrt{\frac{{{2}}}{d}\sum_{i=1}^{d}I\left(V(i)\land
Y^{T}\right)}\right],$

where the second inequality follows from the triangle inequality, the third is
Pinsker’s inequality, and the fourth is Jensen’s inequality. ∎

#####  3 Average information bounds

The next step in our proof is to bound the average mutual information that
emerged in Section 2. A general recipe for bounding this average mutual
information has been given recently in [3], which we recall below.

Let $\\{\mathbf{p}_{v},v\in\\{-1,1\\}^{d}\\}$ be a family of distributions
over some domain $\mathcal{X}$ and $\mathcal{W}$ be a fixed channel family.
For $v\in\\{-1,1\\}^{d}$ and $i\in[d]$, denote by $v^{\oplus i}$ the element
of $\\{-1,1\\}^{d}$ obtained by flipping the $i$th coordinate of $v$. For a
fixed $v$, we obtain $T$ independent samples $X_{1},\dots,X_{T}$ from
$\mathbf{p}_{v}$. Let $Y_{1},\dots,Y_{T}$ be the output of channels selected
from the channel family $\mathcal{W}$ by an adaptive channel selection
strategy (see Section 1) when input to the channel at time $t$ is $X_{t}$,
$1\leq t\leq T$.444The bound in [3] allows even shared randomness $U$ in its
definition of interactive protocols. We have omitted $U$ in the description
for simplicity.

For $V$ distributed uniformly on $\\{-1,1\\}^{d}$, we are interested in
bounding $(1/d)\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)$. In [3], different
bounds were given for this quantity under different assumptions. We state
these assumptions below.

######  Assumptions 5.4.

For every $v\in\\{-1,1\\}^{d}$ and $i\in[d]$, there exists
$\phi_{v,i}\colon\mathcal{X}\to\mathbb{R}$ such that
$\mathbb{E}_{\mathbf{p}_{v}}\left[\phi_{v,i}^{2}\right]=1$,
$\mathbb{E}_{\mathbf{p}_{v}}\left[\phi_{v,i}\phi_{v,j}\right]=\mathbbm{1}_{\\{i=j\\}}$
holds for all $i,j\in[d]$, and

$\frac{d\mathbf{p}_{v^{\oplus i}}}{d\mathbf{p}_{v}}=1+\gamma\phi_{v,i},$

where $\gamma\in\mathbb{R}$ is a fixed constant independent of $v,i$.

######  Assumptions 5.5.

There exists some $\kappa_{\mathcal{W}}\geq 1$ such that

$\max_{v\in\\{-1,1\\}^{d}}\max_{y\in\mathcal{Y}}\sup_{W\in\mathcal{W}}\frac{\mathbb{E}_{\mathbf{p}_{v^{\oplus
i}}}\left[W(y\mid X)\right]}{\mathbb{E}_{\mathbf{p}_{v}}\left[W(y\mid
X)\right]}\leq\kappa_{\mathcal{W}}.$

######  Assumptions 5.6.

There exists some $\sigma\geq 0$ such that, for all $v\in\\{-1,1\\}^{d}$, the
vector $\phi_{v}(X):=(\phi_{v,i}(X))_{i\in[d]}\in\mathbb{R}^{d}$ is
$\sigma^{2}$-subgaussian for $X\sim\mathbf{p}_{v}$.555Recall that a random
variable $Y$ is $\sigma^{2}$-subgaussian if $\mathbb{E}\left[Y\right]=0$ and
$\mathbb{E}\left[e^{\lambda Y}\right]\leq e^{\sigma^{2}\lambda^{2}/2}$ for all
$\lambda\in\mathbb{R}$; and that a vector-valued random variable $Y$ is
$\sigma^{2}$-subgaussian if its projection $\langle{Y,u}\rangle$ is
$\sigma^{2}$-subgaussian for every unit vector $u$. Further, for any fixed
$z$, the random variables $\phi_{v,i}(X)$ are independent across $i\in[d]$.

We then have the following bound local privacy constraints.

######  Theorem 5.7 ([3, Corollary 6]).

Consider $\\{\mathbf{p}_{v},v\in\\{-1,1\\}^{d}\\}$ satisfying Assumption 5.4
and the channel family $\mathcal{W}=\mathcal{W}_{{\tt priv},\varepsilon}$. Let
$V$ be distributed uniformly over $\\{-1,1\\}^{d}$ and $Y^{T}$ be the output
of channels selected by the optimization algorithm as above. Then, we have

$\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)\leq
T\cdot\frac{\gamma^{2}}{2}\cdot e^{\varepsilon}(e^{\varepsilon}-1)^{2}.$

For the case of communication constraints, we have the analogous statement
below:

######  Theorem 5.8 ([3, Corollary 6]).

Consider $\\{\mathbf{p}_{v},v\in\\{-1,1\\}^{d}\\}$ satisfying Assumptions 5.4
and 5.5 and the channel family $\mathcal{W}=\mathcal{W}_{{\tt com},r}$. Let
$V$ be distributed uniformly over $\\{-1,1\\}^{d}$ and $Y^{T}$ be the output
of channels selected by the optimization algorithm as above. Then, we have

$\sum_{i=1}^{d}I\left(V(i)\land
Y^{T}\right)\leq\frac{1}{2}\kappa_{\mathcal{W}_{{\tt com},r}}\cdot
T\gamma^{2}(2^{r}\land d).$

Moreover, if Assumption 5.6 holds as well, we have

$\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)\leq(\ln
2)\kappa_{\mathcal{W}_{{\tt com},r}}\,\sigma^{2}\cdot T\gamma^{2}r.$

Finally, we derive a bound for the oblivious sampling channel family.

######  Theorem 5.9.

Consider $\\{\mathbf{p}_{v},v\in\\{-1,1\\}^{d}\\}$ satisfying Assumption 5.4
and the channel family $\mathcal{W}=\mathcal{W}_{{\tt obl}}$. Let $V$ be
distributed uniformly over $\\{-1,1\\}^{d}$ and $Y^{T}$ be the output of
channels selected by the optimization algorithm as above. Further, assume that
$|\mathcal{X}|<\infty$. Then, we have

$\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)\leq\frac{C}{2}\cdot T\gamma^{2},$

where the constant $C$ depends only on
$\\{\mathbf{p}_{v},v\in\\{-1,+1\\}^{d}\\}$ and, denoting
$\mathcal{X}_{i}:=\\{x(i):x\in\mathcal{X}\\}$, is given by

$C=(\max_{i\in[d]}|\mathcal{X}_{i}|-1)\cdot\max_{x\in\mathcal{X}}\max_{v\in\\{-1,+1\\}^{d}}\max_{i\in[d]}\frac{\mathbf{p}_{v^{\oplus
i}}(X(i)=x(i))}{\mathbf{p}_{v}(X(i)=x(i))}.$

###### Proof.

We recall another result from [3, Theorem 5]: Under Assumptions 5.4 and 5.5,
we have666This is the general bound underlying Theorem 5.7.

$\sum_{i=1}^{d}I\left(V(i)\land
Y^{T}\right)\leq\frac{1}{2}\kappa_{\mathcal{W}_{\tt obl}}\cdot
T\gamma^{2}\max_{v\in\\{-1,1\\}^{d}}\max_{W\in\mathcal{W}_{\tt
obl}}\sum_{y\in\mathcal{Y}}\frac{\operatorname{Var}_{\mathbf{p}_{v}}[W(y\mid
X)]}{\mathbb{E}_{\mathbf{p}_{v}}\left[W(y\mid X)\right]}.$

We now evaluate various parameters involved in this bound. Let $W$ be a
oblivious sampling channel specified by the probability vector
$(p_{i})_{i\in[d]}.$ Note that a channel $W\in\mathcal{W}_{{\tt obl}}$ can be
equivalently viewed as having output alphabet $\mathcal{Y}=\\{(i,z)\colon
z\in\mathcal{X}_{i},i\in[d]\\}$. Recall that for an input $x$, the channel
output is $x(i)$ with probability $p_{i}$, $i\in[d]$, $i.e.$, for $y=(i,z)$,
$W(y\mid x)=p_{i}\mathbbm{1}_{\\{x(i)=z\\}}$. Thus, we have

$\displaystyle\sum_{y\in\mathcal{Y}}\frac{\operatorname{Var}_{\mathbf{p}_{v}}[W(y\mid
X)]}{\mathbb{E}_{\mathbf{p}_{v}}\left[W(y\mid X)\right]}$
$\displaystyle=\sum_{i=1}^{d}\sum_{z\in\mathcal{X}_{i}}\frac{p_{i}^{2}\Pr\left(X(i)=z\right)-p_{i}^{2}\Pr\left(X(i)=z\right)^{2}}{p_{i}\Pr\left(X(i)=z\right)}$
$\displaystyle=\sum_{i=1}^{d}p_{i}(|\mathcal{X}_{i}|-1)$
$\displaystyle\leq\max_{i\in[d]}|\mathcal{X}_{i}|-1.$

Furthermore, proceeding similarly, we get that Assumption 5.5 holds as well
with

$\kappa_{\mathcal{W}_{\tt
obl}}=\max_{x\in\mathcal{X}}\max_{v\in\\{-1,+1\\}^{d}}\max_{i\in[d]}\frac{\mathbf{p}_{v^{\oplus
i}}(X(i)=x(i))}{\mathbf{p}_{v}(X(i)=x(i))}.$

The proof is completed by combining the bounds above. ∎

#####  4 The difficult instances for our lower bounds

With our general tools ready, we now describe the precise constructions of
function families we use to get our lower bounds. We first provide the details
of a family $\mathcal{G_{\tt c}}(a,b)$ of convex functions, before turning to
$\mathcal{G_{\tt sc}}(a,b,\delta,\theta)$, our family of hard instances for
the strongly convex setting. In both cases, our families of hard instances are
parameterized (by $a,b$ and $a,b,\delta,\theta$, respectively), and setting
those parameters carefully will enable us to prove our various results.

###### Difficult functions for the convex family.

To prove lower bounds for the convex family, we will use the class of
functions $\mathcal{G_{\tt c}}(a,b)$ below, parameterized by $a,b>0$ and
defined on the domain $\mathcal{X}$ as follows:

$\displaystyle\mathcal{X}=\\{x\in\mathbb{R}^{d}:\|x\|_{\infty}\leq b\\},$
$\displaystyle g_{v}(x)=a\cdot\sum_{i=1}^{d}|x(i)-v(i)\cdot b|,\quad\forall
x\in\mathcal{X},v\in\\{-1,1\\}^{d},\text{ and}$ $\displaystyle\mathcal{G_{\tt
c}}=\\{g_{v}(x)\colon v\in\\{-1,1\\}^{d}\\}.$ (13)

Observe that the class $\mathcal{G_{\tt c}}$ satisfies the conditions in
Assumption 5.1 with $g_{i,1}(x)=a|x(i)-b|$ and $g_{i,-1}(x)=a|x(i)+b|$ and
$\mathcal{X}_{i}=[-b,b]$ for all $i\in[d].$ Further, we can bound the
discreprency metric for this class as follows.

######  Lemma 5.10.

For the class of functions $\mathcal{G_{\tt c}}$ defined in (4), we have
$\psi(\mathcal{G_{\tt c}})\geq 2ab$.

###### Proof.

Note that $\min_{x\in[-b,b]}g_{i,1}(x)=\min_{x\in[-b,b]}g_{i,-1}(x)=0$.
Therefore, for all $i\in[d]$,

$\psi_{i}(\mathcal{G_{\tt
c}})=\min_{x\in[-b,b]}\left(a|x(i)-b|+a|x(i)+b|\right)\geq 2ab,$

where the inequality follows from the triangle inequality. ∎

###### Difficult functions for the strongly convex family.

To prove lower bounds for the strongly convex family, we will use the class of
functions $\mathcal{G_{\tt sc}}(a,b,\delta,\theta)$, parameterized by $a,b>0$,
$\delta>0$, and $\theta\in[0,1]$, and defined on the domain $\mathcal{X}$ as
follows:

$\displaystyle\mathcal{X}=\\{x\in\mathbb{R}^{d}:\|x\|_{\infty}\leq b\\},$
$\displaystyle g_{v}(x)=a\sum_{i=1}^{d}\left(\frac{1+2\delta
v(i)}{2}f^{+}_{i}(x)+\frac{1-2\delta v(i)}{2}f^{-}_{i}(x)\right),\quad\forall
x\in\mathcal{X},v\in\\{-1,1\\}^{d},\text{ and}$ $\displaystyle\mathcal{G_{\tt
sc}}=\\{g_{v}(x)\colon v\in\\{-1,1\\}^{d}\\},$ (14)

where $f^{+}_{i}$ and $f^{-}_{i}$, for $i\in[d]$, are given by

$\displaystyle f^{+}_{i}(x)$ $\displaystyle=\theta
b|x(i)+b|+\frac{1-\theta}{4}(x(i)+b)^{2},$ (15) $\displaystyle f^{-}_{i}(x)$
$\displaystyle=\theta b|x(i)-b|+\frac{1-\theta}{4}(x(i)-b)^{2},$ (16)

for all $x\in\mathcal{X}$. We can check that, for every $v\in\\{-1,1\\}^{d}$,
the function $g_{v}$ is then $\gamma$-strongly convex for
$\gamma:=a\cdot\frac{1-\theta}{4}$. Moreover, we have the following bound for
the discrepancy metric.

######  Lemma 5.11.

For the class of functions $\mathcal{G_{\tt sc}}$ defined in (4), if
$\frac{1-\theta}{1+\theta}\geq 2\delta$ then $\psi(\mathcal{G_{\tt
sc}})\geq\frac{2ab^{2}\delta^{2}}{1-\theta}\,.$

###### Proof.

This follows from similar calculations as in [5, Appendix A]; we provide the
proof here for completeness. Fixing any $v\in\\{-1,1\\}^{d}$, we first note
that by definition of $\mathcal{G_{\tt sc}}$, the function $g_{v}$ can be
indeed be decomposed as $g_{v}(x)=\sum_{i=1}^{d}g_{i,v(i)}(x_{i})$ for
$x\in\mathcal{X}$ (i.e., $\|x\|_{\infty}\leq b$), where, for $i\in[d]$,
$\nu\in\\{-1,1\\}$ and $y\in\mathcal{X}_{i}:=[-b,b]$,

$\displaystyle g_{i,\nu}(y)$
$\displaystyle=a\left(\frac{1+2\delta\nu}{2}\left(\theta
b|y+b|+\frac{1-\theta}{4}(y+b)^{2}\right)+\frac{1-2\delta\nu}{2}\left(\theta
b|y-b|+\frac{1-\theta}{4}(y-b)^{2}\right)\right)$
$\displaystyle=a\left(\frac{1-\theta}{4}y^{2}+\frac{1+3\theta}{4}b^{2}+\delta\nu(1+\theta)by\right)$

where the second line relies on the fact that $|y+b|=y+b$ and $|y-b|=b-y$ for
$|y|\leq b$. One can easily see, e.g., by differentiation, that $g_{i,\nu}$ is
minimized at $y^{\ast}:=-2\delta\nu\frac{1+\theta}{1-\theta}b$ which does
satisfy $|y^{\ast}|\leq b$ given our assumption $\frac{1-\theta}{1+\theta}\geq
2\delta$. It follows that
$\min_{y\in\mathcal{X}_{i}}g_{i,1}(y)=\min_{y\in\mathcal{X}_{i}}g_{i,-1}(y)=ab^{2}\left(\frac{1+3\theta}{4}-\delta^{2}\frac{(1+\theta)^{2}}{1-\theta}\right)$.
Similarly, we have, for $y\in\mathcal{X}_{i}$,

$\displaystyle g_{i,1}(y)+g_{i,-1}(y)$
$\displaystyle=a\left(\frac{1-\theta}{2}y^{2}+\frac{1+3\theta}{2}b^{2}\right)$

which is minimized at $y^{\ast}=0$, where it takes value
$ab^{2}\frac{1+3\theta}{2}$. Putting it together,

$\psi_{i}(\mathcal{G_{\tt
sc}})=\min_{y\in\mathcal{X}_{i}}(g_{i,1}(y)+g_{i,-1}(y))-(\min_{y\in\mathcal{X}_{i}}g_{i,1}(y)+\min_{y\in\mathcal{X}_{i}}g_{i,-1}(y))=2ab^{2}\delta^{2}\frac{(1+\theta)^{2}}{1-\theta}\,.$

Finally, $\psi(\mathcal{G_{\tt sc}})=\min_{i\in[d]}\psi_{i}(\mathcal{G_{\tt
sc}})=2ab^{2}\delta^{2}\frac{(1+\theta)^{2}}{1-\theta}\geq\frac{2ab^{2}\delta^{2}}{1-\theta}$,
as claimed. ∎

#####  5 Convex Lipschitz functions for $p\in[1,2]$: Proof of Theorems 4.1,
4.4, and 4.7

We first prove Theorems 4.1 and 4.4, our lower bounds on optimization of
convex functions for $p\in[1,2]$ under privacy and communication constraints,
respectively. We consider the class of functions $\mathcal{G}_{\tt c}$ defined
in (4) with parameters $a:=2B\delta/d^{1/q}$ and $b:=D/(2d^{1/p})$. That is,
$\mathcal{X}=\\{x\in\mathbb{R}^{d}:\|x\|_{\infty}\leq D/(2d^{1/p})\\}$ and

$g_{v}(x):=\frac{2B\delta}{d^{1/q}}\sum_{i=1}^{d}\left|x(i)-\frac{v(i)D}{2d^{1/p}}\right|\qquad
x\in\mathcal{X},v\in\\{-1,1\\}^{d}.$ (17)

Note that the gradient of $g_{v}$ is equal to $-2B\delta v/d^{1/q}$ at every
$x\in\mathcal{X}$.

For each $g_{v}$, consider the corresponding gradient oracle $O_{v}$ which
outputs independent values for each coordinate, with the $i$th coordinate
taking values $-B/d^{1/q}$ and $B/d^{1/q}$ with probabilities $(1+2\delta
v(i))/2$ and $(1-2\delta v(i))/2$, respectively, for some parameter $\delta>0$
to be suitably chosen later.

Clearly, $\mathcal{X}\in\mathbb{X}_{p}(D)$ and all the functions $g_{v}$ and
the corresponding oracles $O_{v}$ belong to the convex function family
$\mathcal{O}_{{\tt c},p}$. We begin by noting that for $V$ distributed
uniformly over $\\{-1,1\\}^{d}$, we have

$\sup_{\mathcal{X}\in\mathbb{X}_{p}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
c},p},T,\mathcal{W}_{{\tt
priv},\varepsilon})\geq\mathbb{E}\left[g_{V}(x_{T})-g_{V}(x_{V}^{\ast})\right],$

where the expectation is over $v$ as well as the randomness in $x_{T}$.

From Lemma 5.3 and 5.10, we have

$\mathbb{E}\left[g_{V}(x_{T})-g_{V}(x_{V}^{\ast})\right]\geq{\frac{d\cdot
ab}{3}\cdot}\left[1-\sqrt{\frac{{{2}}}{d}\sum_{i=1}^{d}I\left(V(i)\land
Y^{T}\right)}\right],$ (18)

where $Y^{T}=(Y_{1},...,Y_{T})$ are the channel outputs for the gradient
estimates supplied by the oracle for the $T$ queries.

Next, we apply the average information bound from Section 3. To do so, observe
that by the definition of our oracle, the oracle output at each time step is
an independent draw from the product distribution $\mathbf{p}_{v}$ on
$\Omega:=\left\\{-\frac{B}{d^{1/q}},\frac{B}{d^{1/q}}\right\\}^{d}$ (in
particular, $\mathbf{p}_{v}$ is the same at each time step, as it does not
depend on the query $x_{t}$ at time step $t$ to the oracle). We treat the
output of the independent outputs of the oracle as i.i.d. samples
$X_{1},...,X_{T}$ in Section 3 and the corresponding channel outputs as
$Y^{T}$. We can check that, for every $i\in[d]$, we have

$\frac{\mathbf{p}_{v^{\oplus i}}(x)}{\mathbf{p}_{v}(x)}=\frac{1+2\delta
v(i)\operatorname{sign}(x(i))}{1-2\delta v(i)\operatorname{sign}(x(i))}$ (19)

for all $x\in\Omega$, and that Assumption 5.4 is satisfied with

$\gamma:=\frac{4\delta}{\sqrt{1-4\delta^{2}}},\qquad\phi_{i,v}(x):=\frac{v(i)\operatorname{sign}(x(i))+2\delta}{\sqrt{1-4\delta^{2}}}\,.$
(20)

Furthermore, noting that Assumption 5.5 always holds with

$\kappa_{\mathcal{W}}=\max_{v\in\\{-1,1\\}^{d}}\max_{x\in\Omega}\max_{i\in[d]}\frac{\mathbf{p}_{v^{\oplus
i}}(x)}{\mathbf{p}_{v}(x)},$

it is satisfied with $\kappa_{\mathcal{W}}=2$ (regardless of $\mathcal{W}$),
as long as $\delta\leq 1/6$, since the right-side above is bounded by $2$ for
such a $\delta$. Finally, Assumption 5.6, is also satisfied as
$(\phi_{i,v}(X))_{i\in[d]}$ for $X\sim\mathbf{p}_{v}$ is
$\sigma^{2}$-subgaussian for $\sigma^{2}:=\frac{1}{1-4\delta^{2}}$.

###### Completing the proof of Theorem 4.1 (LDP constraints).

From Theorem 5.7 and the bounds derived above, we have

$\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)\leq
T\cdot\frac{8\delta^{2}}{1-4\delta^{2}}\cdot
e^{\varepsilon}(e^{\varepsilon}-1)^{2},$

and therefore,

$\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)\leq c\cdot
T\delta^{2}\varepsilon^{2},$

where $c:=9e(e-1)^{2}$ (recalling that $\varepsilon\in(0,1]$ and $\delta\leq
1/6$). Substituting this bound on the average mutual information in (18) along
with the values of $a$ and $b$, we have

$\mathbb{E}\left[g_{V}(x_{T})-g_{V}(x_{V}^{\ast})\right]\geq{\frac{DB\delta}{3}\cdot}\left[1-\sqrt{\frac{{{2}}cT\delta^{2}\varepsilon^{2}}{d}}\right].$

Upon setting $\delta:=\sqrt{\frac{d}{{{8}}cT\varepsilon^{2}}}$, we get

$\mathbb{E}\left[g_{V}(x_{T})-g_{V}(x_{V}^{\ast})\right]\geq\frac{1}{12\sqrt{{{2}}c}}\cdot\frac{DB}{\sqrt{T}}\cdot\sqrt{\frac{d}{\varepsilon^{2}}},$

where we require $T\geq\frac{9}{{{2}}c}\cdot\frac{d}{\varepsilon^{2}}$ in
order to enforce $\delta\leq 1/6$. ∎

###### Completing the proof of Theorem 4.4 (Communication constraints).

From Theorem 5.8 and $\gamma$, $\sigma$, and $\kappa_{\mathcal{W}}$ set as
discussed above, we have

$\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)\leq\frac{32(\ln
2)}{(1-4\delta^{2})^{2}}\cdot T\delta^{2}r,$

whereby, using $\delta\leq 1/6$,

$\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)\leq 29T\delta^{2}r.$

Substituting this bound on mutual information in (18) along with the values of
$a$ and $b$, we have

$\mathbb{E}\left[g_{V}(x_{T})-g_{V}(x_{V}^{\ast})\right]\geq\frac{DB\delta}{3}\cdot\left[1-\frac{1}{\sqrt{d}}\cdot\sqrt{{{58}}T\delta^{2}r}\right].$

Setting $\delta:=\sqrt{\frac{d}{{{232}}rT}}$, we finally get

$\mathbb{E}\left[g_{V}(x_{T})-g_{V}(x_{V}^{\ast})\right]\geq\frac{1}{12\sqrt{{{58}}}}\cdot\frac{DB}{\sqrt{T}}\cdot\sqrt{\frac{d}{r}},$

where we require $T\geq\frac{9}{{{58}}}\cdot\frac{d}{r}$ in order to enforce
$\delta\leq 1/6$. ∎

######  Remark 7.

Finally, we remark that the lower bound as in Theorem 4.4 also holds when the
communication constraint of $r$ bits is satisfied in expectation and not in
the strict worst-case sense. The modification to the proof above is minimal.
The only change is that the mutual information term is now bounded by using a
strong data processing inequality from [25]. This bound holds for variable-
length quantizers that satisfy the communication constraints in expectation,
as opposed to the current bound from [3], which only holds for fixed-length
quantizers. Specifically, from [25, Proposition 2], we have that

$\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)\leq cT\delta^{2}r,$

when the communication channel restricts the length of the outputs $Y_{t}$ to
$r$ bits in expectation. A caveat here is that the strong data processing
inequality from [25] holds only for nonadaptive channel selection strategies.
Thus we have the same lower bound on optimization error of family
$\mathcal{O}_{{\tt c},p}$, $p\in[1,2],$ as in Theorem 4.4 even when the
communication constraints are satisfied in expectation as long as the gradient
processing is done in a nonadaptive manner.

###### Completing the proof of Theorem 4.7 (Computational constraints).

Note that the sets $\mathcal{X}_{i}$s in Theorem 5.9 have
$|\mathcal{X}_{i}|=2$ for our oracle. Further,

$\frac{\mathbf{p}_{v^{\oplus
i}}(X(i)=x(i))}{\mathbf{p}_{v}(X(i)=x(i))}=\frac{\mathbf{p}_{v^{\oplus
i}}(x)}{\mathbf{p}_{v}(x)}=\frac{1+2\delta
v(i)\operatorname{sign}(x(i))}{1-2\delta v(i)\operatorname{sign}(x(i))}\leq
2,$

when $\delta\leq 1/6$. Thus, the constant $C$ in Theorem 5.9 is less than $2$,
whereby

$\sum_{i=1}^{d}I\left(V(i)\land
Y^{T}\right)\leq\frac{16\delta^{2}}{1-4\delta^{2}}\cdot T,$

whereby, using $\delta\leq 1/6$,

$\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)\leq 18T\delta^{2}.$

Substituting this bound on mutual information in (18) along with the values of
$a$ and $b$, we have

$\mathbb{E}\left[g_{V}(x_{T})-g_{V}(x_{V}^{\ast})\right]\geq\frac{DB\delta}{3}\cdot\left[1-\frac{1}{\sqrt{d}}\cdot\sqrt{{{36}}T\delta^{2}}\right].$

Setting $\delta:=\sqrt{\frac{d}{{{144}}T}}$, we finally get

$\mathbb{E}\left[g_{V}(x_{T})-g_{V}(x_{V}^{\ast})\right]\geq\frac{1}{{{72}}}\cdot\frac{DB\sqrt{d}}{\sqrt{T}},$

where we require $T\geq\frac{d}{{{4}}}$ in order to enforce $\delta\leq 1/6$.

#####  6 Convex Lipschitz functions for $p\in(2,\infty]$: Proof of Theorems
4.2 and 4.5

Next, we establish Theorems 4.2 and 4.5, the analogous lower bounds on
optimization of convex functions when $p\in[2,\infty)$. We again consider the
class of functions $\mathcal{G}_{\tt c}$ defined in (4), this time with
parameters $a:=2B\delta/d$ and $b:=D/(2d^{1/p})$ That is, here
$\mathcal{X}=\\{x:\|x\|_{\infty}\leq D/(2d^{1/p})\\}$ and

$g_{v}(x):=\frac{2B\delta}{d}\sum_{i=1}^{d}\left|x(i)-\frac{v(i)D}{2d^{1/p}}\right|.\quad\forall
x\in\mathcal{X},v\in\\{-1,1\\}^{d}.$

It follows that the gradient of $g_{v}$ is equal to $-2B\delta v/d$ at every
$x\in\mathcal{X}$.

For each $g_{v}$, consider then the gradient oracle $O_{v}$ which outputs $0$
in all but a randomly chosen coordinate; if that coordinate is $i$, it takes
values $-B$ and $B$ with probabilities $\frac{1+2\delta v(i))}{2d}$ and
$\frac{1-2\delta v(i)}{2d}$, respectively, for some parameter
$\delta\in(0,1/6]$ to be suitably chosen later. Thus, the oracle is no longer
a product distribution.

Clearly, $\mathcal{X}\in\mathbb{X}_{p}(D)$ and all the functions $g_{v}$ and
the corresponding oracles $O_{v}$ belong to the convex function family
$\mathcal{O}_{{\tt c},p}$. Proceeding as in Section 5, we get for a uniformly
distributed $V$ that

$\mathbb{E}\left[g_{V}(x_{T})-g_{V}(x_{V}^{\ast})\right]\geq{\frac{DB\delta}{3d^{1/p}}\cdot}\left[1-\sqrt{\frac{1}{d}\sum_{i=1}^{d}{{2}}I\left(V(i)\land
Y^{T}\right)}\right].$ (21)

Further, proceeding as in the previous section to bound the average
information, we note that the oracle outputs independent samples from the
distribution $\mathbf{p}_{v}$ on $\Omega:=\left\\{-B,0,B\right\\}^{d}$ at each
time. It can be checked easily that, for every $i\in[d]$, the expression of
the ratio $\frac{\mathbf{p}_{v^{\oplus i}}}{p_{v}}$ given in (19) still holds
(as only the denominators of the Bernoulli parameters have changed, and they
cancel out in the ratio), and that Assumption 5.4 is satisfied with the
following $\gamma$, $\phi_{i,v}$s:

$\gamma:=\frac{1}{\sqrt{d}}\cdot\frac{4\delta}{\sqrt{1-4\delta^{2}}},\qquad\phi_{i,v}(x):=\sqrt{d}\cdot\frac{v(i)\operatorname{sign}(x(i))+2\delta}{\sqrt{1-4\delta^{2}}}\,.$
(22)

Observe the difference with the expressions from the previous section
(specifically, (20)), as the orthonormality assumption now crucially
introduces a factor $1/\sqrt{d}$ in the value of $\gamma$. Finally, because we
will enforce $\delta\leq 1/6$ we also can take $\kappa_{\mathcal{W}_{{\tt
com},r}}=2$ for the communication constraints, as before. We remark that
$\phi_{i,v}(X)$ is no longer subgaussian.

###### Completing the proof of Theorem 4.2 (LDP constraints).

From Theorem 5.7 and the value of $\gamma$ above, we get, analogously to the
previous section,

$\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)\leq
c\cdot\frac{T\delta^{2}\varepsilon^{2}}{d},$

where $c:=9e(e-1)^{2}$ (recalling that $\varepsilon\in(0,1]$ and $\delta\leq
1/6$). Substituting this bound on mutual information in (21), we obtain

$\mathbb{E}\left[g_{V}(x_{T})-g_{V}(x_{V}^{\ast})\right]\geq\frac{DB\delta}{3d^{1/p}}\,\left[1-\sqrt{\frac{{{2}}cT\delta^{2}\varepsilon^{2}}{d^{2}}}\right].$

Optimizing over $\delta$, we set
$\delta:=\sqrt{\frac{d^{2}}{8cT\varepsilon^{2}}}$ and get

$\mathbb{E}\left[g_{V}(x_{T})-g_{V}(x_{V}^{\ast})\right]\geq\frac{1}{12\sqrt{{{2}}c}}\cdot\frac{DBd^{1/2-1/p}}{\sqrt{T}}\cdot\sqrt{\frac{d}{\varepsilon^{2}}},$

where we require $T\geq\frac{9}{{{2}}c}\cdot\frac{d^{2}}{\varepsilon^{2}}$ in
order to guarantee $\delta\leq 1/6$. This concludes the proof. ∎

###### Completing the proof of Theorem 4.5 (Communication constraints).

We prove the two parts of the lower bounds separately, starting with the
first. From Theorem 5.8 and the setting of $\gamma$ and $\kappa_{\mathcal{W}}$
as above, we have

$\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)\leq\frac{16}{1-4\delta^{2}}\cdot
T\delta^{2}\frac{2^{r}\land d}{d},$

whereby, using $\delta\leq 1/6$,

$\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)\leq 18T\delta^{2}\frac{2^{r}\land
d}{d}.$

Substituting this bound on mutual information in (21), we have

$\mathbb{E}\left[g_{V}(x_{T})-g_{V}(x_{V}^{\ast})\right]\geq\frac{DB\delta}{3d^{1/p}}\cdot\left[1-\frac{1}{\sqrt{d}}\cdot\sqrt{{{36}}T\delta^{2}\frac{2^{r}\land
d}{d}}\right].$

Setting $\delta:=\sqrt{\frac{d^{2}}{{{144}}(2^{r}\land d)T}}$, we finally get

$\mathbb{E}\left[g_{V}(x_{T})-g_{V}(x_{V}^{\ast})\right]\geq\frac{1}{{{72}}}\cdot\frac{DBd^{1/2-1/p}}{\sqrt{T}}\cdot\sqrt{\frac{d}{2^{r}\land
d}},$

where we require $T\geq\frac{1}{{{4}}}\cdot\frac{d^{2}}{2^{r}\land d}$ in
order to guarantee $\delta\leq 1/6$.

The second bound follows by noting that the lower bound in Theorem 4.4 is
still valid. Finally, since $\frac{d^{2}}{2^{r}\land d}\geq\frac{d}{r}$ for
all $1\leq r\leq d$, both bounds apply whenever
$T=\Omega\left(\frac{d^{2}}{2^{r}\land d}\right)$, as claimed. ∎

#####  7 Strongly convex functions: Proof of Theorem 4.3, 4.6, and 4.8

Next, we establish our lower bounds on strongly convex optimization. We
consider the class of functions $\mathcal{G}_{\tt sc}$ defined in (4) with
parameters $a:=B/(\sqrt{d}b)$ and $b:=D/(2\sqrt{d}).$ That is,
$\mathcal{X}=\\{x:\|x\|_{\infty}\leq D/(2\sqrt{d})\\}$, and, for every
$x\in\mathcal{X}$ and $v\in\\{-1,1\\}^{d}$,

$g_{v}(x):=\frac{B}{b\cdot\sqrt{d}}\sum_{i=1}^{d}\frac{1+2\delta
v(i)}{2}f^{+}_{i}(x)+\frac{1-2\delta v(i)}{2}f^{-}_{i}(x),$

and

$f^{+}_{i}(x)=\theta
b|x(i)+b|+\frac{1-\theta}{4}(x(i)+b)^{2}~{}\text{and}~{}f^{-}_{i}(x)=\theta
b|x(i)-b|+\frac{1-\theta}{4}(x(i)-b)^{2}.$

Moreover, in order to ensure that the every $g_{v}$ is $\gamma$-strongly
convex, we choose $\theta:=1-\frac{4\gamma}{a}$ (so that
$a\frac{1-\theta}{4}=\gamma$). It remains to specify $\delta$, which we will
choose such that $0<\delta\leq\frac{1}{2}\cdot\frac{1-\theta}{1+\theta}$ in
the course of the proof.

For each $g_{v}$, consider the gradient oracle $O_{v}$ which on query $x$
outputs independent values for each coordinate, with the $i$th coordinate
taking values $\frac{B}{b\sqrt{d}}\cdot\frac{\partial f^{+}_{i}(x)}{\partial
x_{i}}$ and $\frac{B}{b\sqrt{d}}\cdot\frac{\partial f^{-}_{i}(x)}{\partial
x_{i}}$ with probabilities $\frac{1+2\delta v(i))}{2}$ and $\frac{1-2\delta
v(i)}{2}$, respectively.

Note that we have $\left|\frac{\partial f^{+}_{i}(x)}{\partial
x_{i}}\right|,\left|\frac{\partial f^{-}_{i}(x)}{\partial x_{i}}\right|\leq b$
for all $x$ and $i$, and therefore the gradient estimate $\hat{g}(x)$ supplied
by the oracle $O_{v}$ at $x$ satisfies $\|\hat{g}(x)\|_{2}^{2}\leq B^{2}$ with
probability one, for every query $x\in\mathcal{X}$. Further, it is clear that
$\mathcal{X}\in\mathbb{X}_{2}(D)$ and all the functions $g_{v}$ and the
corresponding oracles $O_{v}$ belong to the strongly convex function family
$\mathcal{O}_{{\tt sc}}$.

Using our assumption that
$\delta\leq\frac{1}{2}\cdot\frac{1-\theta}{1+\theta}$, we obtain by Lemma 5.11

$\psi(\mathcal{G}_{\tt
sc})\geq\frac{2ab^{2}\delta^{2}}{1-\theta}=\frac{2a^{2}b^{2}\delta^{2}}{4\gamma}=\frac{B^{2}\delta^{2}}{2d\gamma},$
(23)

where we first plug in $a(1-\theta)=4\gamma$ and then substitute for $a$ and
$b$.

###### Completing the proof of Theorem 4.6 (Communication constraints).

By proceeding as in Section 5, from Lemma 5.3 and using the inequality (23)
above, we have

$\sup_{\mathcal{X}\in\mathbb{X}_{2}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
sc}},T,\mathcal{W}_{{\tt
com},r})\geq\frac{B^{2}\delta^{2}}{12\gamma}\left[1-\sqrt{\frac{{{2}}}{d}\sum_{i=1}^{d}I\left(V(i)\land
Y^{T}\right)}\right].$ (24)

It remains to bound $\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)$ to complete
the proof. Note that unlike the proof in Section 5, the gradient estimates
have different distributions for different $x$. However, for a point $x$ we
can still express the gradient estimate $\hat{z}(x)$ of $g_{v}(x)$ given by
$O_{v}$ as follows: abbreviating $f^{\prime+}_{i}(x):=\frac{\partial
f^{+}_{i}(x)}{\partial x_{i}}$ and $f^{\prime-}_{i}(x):=\frac{\partial
f^{-}_{i}(x)}{\partial x_{i}}$, we have

$\displaystyle\hat{z}(x)(i)=aZ_{i}f^{\prime+}_{i}(x)+a(1-Z_{i})f^{\prime-}_{i}(x),$
(25)

where $Z_{i}\sim\operatorname{Ber}(1/2+\delta v(i))$ and the $Z_{i}$’s are
mutually independent. Thus, for a fixed $x$, $\hat{z}(x)$ can be viewed as a
function of $\\{Z_{i}\\}_{i\in[d]}$. Furthermore, for a channel
$W\in\mathcal{W}_{{\tt com},r}$ consider the channel $W^{\prime}_{x}$ which
first passes the Bernoulli vector $\\{Z_{i}\\}_{i\in[d]}$ through the function
$\hat{z}(x)(i)$ and the resulting output is passed through the channel $W$.
This composed channel $W_{x}$ belongs to $\mathcal{W}_{{\tt com},r}$, too.

Therefore, we can treat the independent copies of $Z\sim\mathbf{p}_{v}$
revealed by the oracle as i.i.d. random variables $X_{1},...,X_{n}$ in Section
3. Further, note that at time $t$, the query is for a point $x_{t}$ which is a
random function of $Y^{t-1}$, and so, $Y^{T}$ can be viewed as the channel
outputs with adaptively selected channels from $\mathcal{W}_{{\tt com},r}$.
Thus, we can apply the bounds in Theorem 5.8.

Doing so, analogously to the computations in Section 5,777As we have, in both
cases, unknown Bernoulli product distribution over $\\{-1,1\\}^{d}$ with bias
vector $\frac{1}{2}+\delta v$. we get

$\sum_{i\in[d]}I(v(i)\wedge\\{Y_{i}\\}_{i\in[T]})\leq\sum_{i=1}^{d}I\left(V(i)\land
Y^{T}\right)\leq c\delta^{2}rT,$

for an appropriate constant $c$, which in view of (24) leads to

$\sup_{\mathcal{X}\in\mathbb{X}_{2}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
sc}},T,\mathcal{W}_{{\tt
com},r})\geq{\frac{B^{2}\delta^{2}}{12\gamma}\cdot}\left[1-\frac{1}{\sqrt{d}}\cdot\sqrt{{{2}}cT\delta^{2}r}\right]=\frac{1}{{{192}}c}\cdot\frac{B^{2}}{\gamma
T}\cdot\frac{d}{r}$

the last equality by setting $\delta:=\sqrt{\frac{d}{{{8}}cTr}}$. Finally,
observe that this choice of $\delta$ indeed satisfies
$\delta<\frac{1}{2}\cdot\frac{1-\theta}{1+\theta}$, as long as
$T\geq{{2}}c\cdot\frac{B^{2}}{D^{2}}\cdot\frac{d}{\gamma^{2}r}$. This
completes the proof. ∎

###### Completing the proof of Theorem 4.3 (Privacy constraints).

Proceeding as in the proof of Theorem 4.6 above, we have the analogue of (24),

$\sup_{\mathcal{X}\in\mathbb{X}_{2}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
sc}},T,\mathcal{W}_{{\tt
priv},\varepsilon})\geq\frac{B^{2}\delta^{2}}{12\gamma}\left[1-\sqrt{\frac{{{2}}}{d}\sum_{i=1}^{d}I\left(V(i)\land
Y^{T}\right)}\right].$

As stated in the proof of Theorem 4.6, the privatization of the gradient
$\hat{z}(x)$ can be viewed as first preprocessing $\\{Z_{i}\\}_{i\in[d]}$ and
the passing the preprocessed output through the LDP channel. Such a composed
channel also belongs to $\mathcal{W}_{{\tt priv},p}$. Thus, we can apply the
bound in Theorem 5.7 and proceed as in the proof of Theorem 4.1 to obtain

$\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)\leq cT\delta^{2}\varepsilon^{2}$

where $c>0$ is an absolute constant. Choosing
$\delta:=\sqrt{\frac{d}{{{8}}cT\varepsilon^{2}}}$, which makes $2\delta$ less
than $\frac{1-\theta}{1+\theta}$ for
$T\geq{{2}}c\cdot\frac{B^{2}}{D^{2}}\cdot\frac{d}{\gamma^{2}\varepsilon^{2}}$,
for some universal positive constant $c$, then yields

$\sup_{\mathcal{X}\in\mathbb{X}_{2}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
sc}},T,\mathcal{W}_{{\tt priv},\varepsilon})\geq c_{0}\cdot\frac{B^{2}}{\gamma
T}\cdot\frac{d}{\varepsilon^{2}}$

for some absolute constant $c_{0}>0$, concluding the proof. ∎

###### Completing the proof of Theorem 4.8 (Computational constraints).

As before, we can get

$\sup_{\mathcal{X}\in\mathbb{X}_{2}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
sc}},T,\mathcal{W}_{\tt
obl})\geq\frac{B^{2}\delta^{2}}{12\gamma}\left[1-\sqrt{\frac{{{2}}}{d}\sum_{i=1}^{d}I\left(V(i)\land
Y^{T}\right)}\right].$

Recall that we can express the subgradient estimate as in (25). Note that for
an oblivious sampling channel $W_{t}$ used at time $t$, specified by a
probability vector $(p_{j})_{j\in[d]}$, the output is given by

$\displaystyle{{Y_{i}=(aZ_{J_{t}}f^{\prime+}_{J_{t}}(x)+a(1-Z_{J_{t}})f^{\prime-}_{J_{t}}(x))e_{J_{t}},}}$

where $J_{t}=j$ with probability $p_{j}$. To proceed, we observe that the
Markov relation $V\text{---}\\{Z_{J_{t}},J_{t}\\}_{t\in[T]}\text{---}{Y^{T}}$
holds. Indeed, we can confirm this by noting that $\\{Z_{J_{t}}\\}_{t\in[T]}$
are generated i.i.d. from $\mathbf{p}_{V}$ and, for each $t\in[T]$, $Y_{t}$ is
a function of $(Y^{t-1},Z_{J_{t}},J_{t})$ and a local randomness $U$ available
only to the optimization algorithm which is independent jointly of $V$ and
$\\{Z_{J_{t}},J_{t}\\}_{t\in[T]}$. It follows that $Y^{T}$ itself is a
function of $U$ and $\\{Z_{J_{t}},J_{t}\\}_{t\in[T]}$, which gives

$\displaystyle{{I\left(V\land
Y^{T}\mid\\{Z_{J_{t}},J_{t}\\}_{t\in[T]}\right)\leq I\left(V\land
U\mid\\{Z_{J_{t}},J_{t}\\}_{t\in[T]}\right)=0.}}$ (26)

From the previous observation, we also get that the Markov relation
$V(i)\text{---}\\{Z_{J_{t}},J_{t}\\}_{t\in[T]}\text{---}{Y^{T}}$ holds for
every $i\in[d]$. Thus, by the data processing inequality for mutual
information, we have

${{\sum_{i=1}^{d}I\left(V(i)\land
Y^{T}\right)\leq\sum_{i=1}^{d}I\left(V(i)\land\\{Z_{J_{t}},J_{t}\\}_{t\in[T]}\right).}}$

Now since vector $(Z_{j})_{j\in[d]}$ is a Bernoulli vector, the mutual
information on the right-side can be bounded by the same computation as in the
proof of Theorem 4.7 using Theorem 5.9. This follows by observing that for all
$t\in[T]$, $(Z_{J_{t}},J_{t})$ is a function of $Z_{J_{t}}e_{J_{t}}$, which in
turn can be seen as a output of the oblivious sampling channel for an input
vector $(Z_{j})_{j\in[d]}$. Therefore, we have

$\sum_{i=1}^{d}I\left(V(i)\land Y^{T}\right)\leq cT\delta^{2}$

for an appropriate constant $c$ and $\delta\leq\frac{1}{6},$ which in view of
(24) leads to

$\sup_{\mathcal{X}\in\mathbb{X}_{2}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
sc}},T,\mathcal{W}_{{\tt
com},r})\geq\frac{B^{2}\delta^{2}}{12\gamma}\left[1-\frac{1}{\sqrt{d}}\cdot\sqrt{{{2}}cT\delta^{2}}\right]=\frac{1}{c_{0}}\cdot\frac{dB^{2}}{\gamma
T},$

where the last identity is obtained by setting
$\delta:=c_{1}\sqrt{\frac{d}{T}}$, where $c_{0}$ and $c_{1}$ are universal
positive constants. Finally, observe that this choice of $\delta$ indeed
satisfies $\delta<\frac{1}{2}\cdot\frac{1-\theta}{1+\theta}$, as long as
$T\geq c_{2}\cdot\frac{B^{2}}{D^{2}}\cdot\frac{d^{2}}{\gamma}$, for some
universal positive constant $c_{2}$. This completes the proof. ∎

####  6 Concluding Remarks

In this chapter, we derived lower bounds on the optimization error incurred by
any first-order algorithm when the stochastic gradients used by the
optimization algorithm need to be further processed to satisfy information
constraints. We also saw that the gradient processing schemes proposed in the
literature and appropriate first-order algorithms almost match our derived
lower bounds in the case of privacy and computational constraints. Therefore,
in the rest of the first part, we will develop gradient compression algorithms
to match the lower bounds for communication-constrained optimization.

###  Chapter 2 Communication-Constrained Optimization over Euclidean Space

####  1 Synopsis

For communication-constrained optimization over the Euclidean Space, where the
subgradient estimate’s norm is almost surely bounded, we present Rotated
Adaptive Tetra-iterated Quantizer (RATQ), a fixed-length quantizer for
subgradient estimates. RATQ is easy to implement and involves only a Hadamard
transform computation and adaptive uniform quantization with appropriately
chosen dynamic ranges. We show that RATQ along with PSGD achieves the lower
bound for communication-constrained optimization over Euclidean Space.

We further extend our results for communication-Constrained optimization over
Euclidean space when the subgradient estimates are mean square bounded. In
this setting, we use a gain-shape subgradient quantizer which separately
quantizes the Euclidean norm and uses RATQ to quantize the normalized unit
norm vector. We establish lower bounds for performance of any optimization
procedure and shape quantizer, when used with a uniform gain quantizer.
Finally, we propose an adaptive quantizer for gain which when used with RATQ
for shape quantizer outperforms uniform gain quantization and is, in fact,
close to optimal.

The results presented in this chapter are from [68] and [69].

####  2 Introduction

In this chapter, we develop new algorithms to match the lower bounds for
communication-constrained optimization over Euclidean Space. More precisely,
we study communication-constrained optimization for convex and $\ell_{2}$
lipschitz function family as well as strongly convex and $\ell_{2}$ lipschitz
function family. We consider two oracle models: the first where the
subgradient estimate’s Euclidean norm is almost surely bounded and the second
where it is mean square bounded. While our lower bounds in Chapter 1 were
derived for the simpler, almost surely bounded oracles, where the subgradient
estimates have their noise almost surely bounded. In this setting, we also
develop algorithms for the more general mean square bounded oracle. Our main
contributions include new quantizers for the two oracle models and theoretical
insights into the limitations imposed by heavy-tailed gradient distributions
admitted under the mean square bounded oracles. A more specific description of
our results and their relation to prior work is provided below.

#####  1 Main contributions

We start with almost surely bounded oracles and consider communication-
constrained optimization for convex and $\ell_{2}$ lipschitz function family.
Our precision-dependent lower bound in Theorem 4.4 shows that no optimization
protocol using a first order oracle and gradient updates of precision $r<d$
bits can have optimization error smaller than roughly $\sqrt{d}/\sqrt{rT}$. In
particular, we need precision exceeding $\Omega(d)$ bits to get the classic
convergence rate of $1/\sqrt{T}$ for convex functions. As our main
contribution, we propose a new fixed-length quantizer we term Rotated Adaptive
Tetra-iterated Quantizer  (RATQ) that along with projected subgradient descent
(PSGD) is merely a factor of $O(\log\log\log\log^{*}d)$ far from this minimum
precision required to attain the $O(1/\sqrt{T})$ convergence rate. In a
different setting, when the precision is fixed upfront to $r$, we modify RATQ
by roughly quantizing and sending only a subset of coordinates of the rotated
vector. We show that this modified version of RATQ is only a factor
$O(\log\log^{*}d)$ far from the optimal convergence rate. For almost sure
bounded oracles, all our results for convex and $\ell_{2}$ lipschitz family
are then extended to strongly convex and $\ell_{2}$ lipschitz family.

For mean square bounded oracles, we state our results for convex and
$\ell_{2}$ lipschitz family. However, most of our results in this setting can
be extended to strongly convex family mutatis mutandis. In this setting, most
of the prior work makes an additional assumption that the gradient norm can be
expressed using only a finite number of bits without accruing any quantization
error. One of our main contributions for mean square bounded oracles is to
analyse the quantization error without any such additional assumptions. For
such oracles, we establish an information theoretic lower bound in Section 1
which shows (using a heavy-tailed oracle) that the precision used for
gain111In the vector quantization literature, the norm of the vector to be
quantized is called the gain and vector normalized by this norm is called the
shape. quantizer must exceed $\log T$ when the gain is quantized uniformly for
$T$ iterations and we seek $O(1/\sqrt{T})$ optimization accuracy. Thus, if
$32$ bits are used to describe the gain using a uniform quantizer, they will
suffice for roughly a billion iterations. Interestingly, we present a new,
adaptive gain quantizer which can attain the same performance using only
$\log\log T$ bits for quantizing gain. In particular, using our scheme, only
$5$ bits assigned for describing gain will suffice for a billion iterations;
these many bits will work for less than 100 iterations using uniform gain
quantizers. In a different setting, when the precision is fixed upfront we
propose a quantizer which along with PSGD achieves the almost optimal
convergence rate.

#####  2 Remarks on techniques

In this work we use adaptive quantizers with multiple dynamic-ranges
$\\{[-M_{i},M_{i}]:i\in[h]\\}$, with possibly a different dynamic range chosen
for each coordinate. Once a dynamic-range $[-M_{i},M_{i}]$ is chosen for a
coordinate, the coordinate is quantized uniformly within this dynamic-range
using $k$ levels. Using a different dynamic-range for each coordinate allows
us to reduce error per coordinate, but costs us in communication since we need
to communicate which $M_{i}$ is used for each coordinate. In devising our
scheme, we need to carefully balance this tradeoff. We do this by taking
recourse to the following observation: when the same dynamic range is chosen
for all coordinates, the mean square error per coordinate roughly grows as

$\displaystyle O\left(\frac{\sum_{i\in[h]}M_{i}^{2}\cdot
p(M_{i-1})}{(k-1)^{2}}\right),$ (1)

where $p(M)$ is the probability of the $\ell_{\infty}$ norm of the input
vector exceeding $M$ and $k$ denotes the number of levels of the uniform
quantizer. This observation allows us to relate the mean square error to the
tail-probabilities of the $\ell_{\infty}$ norm of the input vector. In
particular, we exploit it to decide on the subvectors which we quantize using
the same dynamic range.

As an aside, we believe that this approach and equation (1), in particular,
will yield very efficient rate-distortion codes for various sources with
different tail probabilities, answering questions of fundamental interest and
having many applications. We point out an application to the classic Gaussian
rate-distortion problem in Chapter 5.

We use another classic trick (see [34]): we transform the input vector before
we apply our adaptive quantizer. In particular, we use a randomized transform
that expresses the input vector over a random basis. The specific choice of
our random transform is determined by our assumption for the gradients, namely
that their $\ell_{2}$ norms are almost surely bounded by $B$.

Drawing from these ideas, we propose the quantizer RATQ for quantizing random
vectors with $\ell_{2}$ norm almost surely bounded by $B$.

We remark that using an adaptively chosen dynamic-range can alternatively be
implemented by transforming the input using a monotone function. This, too, is
a classic technique in quantization known as companding ($cf.$ [34]).
Companding is known as a popular alternative to entropic coding for fixed-
length codes. However, to the best of our knowledge, this work is the first to
combine it with other techniques and rigorously analyze it for the $\ell_{2}$
norm bounded vector quantization problem. Perhaps it is a bit surprising that
this combination of classic technique was not analysed for constructing an
efficient covering of the unit Euclidean ball, the problem underlying our
quantization problem.

Moving to oracles with mean square bounded $\ell_{2}$ norms, we take recourse
to gain-shape quantizers and quantize the (normalized) shape vector using
RATQ. However, unlike prior work, we rigorously treat gain quantization. Our
proposed quantizer for gain is once again an adaptive quantizer.

Our lower bounds derived in Chapter 1 use almost surely bounded oracles as the
difficult oracle. However, this only allows us to obtain lower bounds for the
almost surely bounded setting. For the mean square bounded setting, we need a
new construction with “heavy tails”. In particular, our proposed heavy-tailed
construction shows a bottleneck for uniform gain quantizers which can be
circumvented by our proposed quantizer, thereby establishing a strict
improvement over uniform gain quantizers.

#####  3 Prior work

Our work is motivated by the results in [88, 9], and we elaborate on the
connection. Specifically, [9] considers a problem very similar to ours. The
paper [88] considers the related problem of distributed mean estimation – we
elaborate on the distributed mean estimation results in Chapter 4 – but the
quantizer and its analysis is directly applicable to distributed optimization.
The two papers present different quantizers that encode each input using a
variable number of bits. Both these quantizers require the optimal expected
precision to achieve the $1/\sqrt{T}$ convergence rate for almost surely
bounded oracles. However, their worst-case (fixed-length) performance maybe
suboptimal. Our proposed quantizer RATQ requires a precision only slightly
more than the optimal precision to achieve the $1/\sqrt{T}$ convergence rate
for almost surely bounded oracles, while still being fixed-length. Moreover,
in the slightly different setting of operating for any precision constraint
$r$ less than the dimension, we significantly improve upon the current state-
of-the-art.

In fact, the problem of designing fixed-length quantizers for almost surely
bounded oracles is closely related to designing small-size covering for the
Euclidean unit ball. There has been a longstanding interest in this problem in
the vector quantization and information theory literature ($cf.$ [92, 34, 47,
19, 55, 27]).

In a slightly different direction, a seminal, but perhaps not so widely known,
result of [100] provides a very simple universal quantizer for random vectors
with independent and identically distributed ($iid$) coordinates, with each
coordinate almost surely bounded. In this scheme, we first quantize each
coordinate uniformly, separately using a “scalar-quantizer,” and then apply a
universal entropic compression scheme to the quantized vector. We note that
the variable-length schemes proposed in [9, 88] are very similar, albeit with
a specific choice of the entropic compression scheme.

All these schemes (the ones in [100, 9, 88]) are variable-length schemes,
while it is desirable to get a fixed-length scheme for the ease of both
protocol and hardware implementation. We remark that indeed [88] presents an
interesting randomly-rotate and quantize fixed-length scheme, but it still
requires communicating $O(\log\log d)$ times more than the optimal fixed-
length quantizer for the unit Euclidean ball given in [92]. To the best of our
knowledge, prior to our work, the quantizer in [88] is the best known
efficient fixed-length quantizer for the unit Euclidean ball.

In fact, a randomized orthogonal transform scheme similar to that in [88]
appeared almost concurrently in [39] as well, where an analysis for Gaussian
source is presented. However, a rate-distortion analysis has not been done in
[39]. Remarkably, an early instance of the “rotated dithering” scheme for
distributing energy equally appears in the image compression literature in
[75], albeit without formal error or performance analysis. Another interesting
scheme was proposed in [8] where nonuniform quantization (using companding)
was combined with dithering. Our adaptive choice of dynamic range for uniform
quantizers is similar, in essence, to companding. But our scheme differs from
the one in [8] in several ways: First, [8] uses the knowledge of input
distribution to design their companding function, whereas we only need
knowledge of the tail behaviour of the input distribution in our setting;
second, we apply a random rotation to our input leading to a universal
quantizer, which is not needed in [8]; and finally, the specific structure of
our quantizer with adaptive dynamic ranges makes it amenable to mean square
error analysis for a large variety of sources.

Another scheme, similar, in spirit, to [88], appears earlier in [62]. In this
scheme, the input vector is preprocessed using a redundant system of vectors
(the resulting representation is called Kashin’s representation) instead of
random rotation as in [88]. In theory, if the underlying system of vectors
satisfies certain desirable properties, then preprocessing the vector in this
manner and then uniformly quantizing each coordinate in the representation
will lead to an orderwise optimal fixed-length quantizer for the unit ball.
Unfortunately, [62] provides only a randomized constructions222Note that
randomly producing the optimal quantizer with high probability is different
from constructing the optimal random quantizer, as we do. The former only
gives high probability guarantees for bounds on loss, but need not yield a
bound for expected loss. for the system of vectors that satisfy the
aforementioned properties with high probability. Thus, the scheme in [62] is
not explicit. Further, as a side remark, we note that the preprocessing step
in [62] requires $O(d^{2}\log d)$ real operations, much worse than the
$O(d\log d)$ real operations required by RATQ.

Another recent independent work [33] presents a different scheme where a
different random transform is used instead of random rotation. The optimal
scheme in [33] is similar to the one in [62] and in essence to classical
information-theoretic schemes ($cf.$ [92], [55]). Specifically, [33] provides
a randomized algorithm that outputs the orderwise optimal quantizer for the
unit ball without an explicit construction. Moreover, the time complexity of
the overall quantization procedure in [33] is much worse than RATQ.

Returning to the literature on quantizers for first order stochastic
optimization, prior works including [9] remain vague about the analysis for
mean square bounded oracles. Most of the works use gain-shape quantizers that
separately quantize the Euclidean norm (gain) and the normalized vector
(shape). But they operate under an engineering assumption: “the standard $32$
bit precision suffices for describing the gain.” One of our goals in this work
is to carefully examine this heuristic. For instance, can we use a simple
uniform quantizer for gain with $32$ bits, or even say $8$ bits?

Independent of our work, a non-uniform quantizer similar to the one we use for
gain-quantization with geometrically increasing dynamic-ranges appears in
[78]. However, there are some key differences between the two quantizers.
First, note that we use this quantizer for gain-quantization, while [78] uses
it to quantize the shape. Second, in the case of our quantizer the
geometrically growing dynamic ranges are further quantized uniformly whereas
[78] chooses to use geometrically growing points as final quantization points.
Third, the analysis of mean square quantization error in this work and [78]
differ significantly. In particular, our mean square analysis follows from the
general principle stated in (1), whereas [78] builds upon the analysis of QSGD
in [9]. Finally, the setting considered in [78] is similar to that of [9]
where quantization is followed by entropic compression. In particular, the
fixed-length performance may be suboptimal for almost surely bounded oracles
and mean square bounded oracles are not handled.

##### Organization

We formalize our problem in the next section and describe our results for
almost surely and mean square bounded oracles in Sections 4 and 5,
respectively, along with some of the shorter proofs. The more elaborate proofs
are provided in Section 6, with additional details relegated to Section 7.

####  3 Setup and preliminaries

#####  1 Setup

In the next two chapters, we develop efficient subgradient compression
algorithms for the setting of communication-constrained first-order
optimization described in the previous Chapter. Our domain $\mathcal{X}$
throughout this chapter has Euclidean diameter less than $D$. That is,

$\displaystyle\mathcal{X}\in\mathbb{X}_{2}(D)=\\{\mathcal{X}^{\prime}:\sup_{x,y\in\mathcal{X}^{\prime}}\|x-y\|_{2}\leq
D.\\}$ (2)

For the domain of optimization $\mathcal{X}$, we develop subgradient
compression schemes for function and oracle families given by
$\mathcal{O}_{{\tt c},2}$ and $\mathcal{O}_{{\tt sc}}$, which are defined in
Definitions 3.3 and 3.6, respectively.

We remark that the typical assumption made on the optimization literature on
the oracle noise is that it is _mean square bounded_. That is, for a query
point $x\in\mathcal{X},$ the oracle random estimates of the subgradient
$\hat{g}(x)$ which for all $x\in\mathcal{X}$ satisfy

$\mathbb{E}\left[\|\hat{g}(x)\|_{2}^{2}|x\right]\leq B^{2},$ (3)

where $\partial f(x)$ denotes the set of subgradients of $f$ at $x$. In this
chapter, we also want to develop schemes for mean square bounded oracles.
Towards that end, we define generalization of class $\mathcal{O}_{{\tt
c},2}^{\tt m}$ below.

######  Definition 3.1 (Convex and $\ell_{2}$ Lipschitz function family for a
mean square bounded oracle $\mathcal{O}_{{\tt c},2}^{\tt m}$).

We denote by $\mathcal{O}_{{\tt c},2}^{\tt m}$ the set of all pairs of
functions and oracles satisfying Assumptions (4), (5), and (3).

Thus the assumption (6) is replaced by (3) for mean square bounded families.
Clearly,

$\displaystyle\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt c},2}^{\tt
m},T,\mathcal{W}_{{\tt
com},r)}\geq\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
c},2},T,\mathcal{W}_{{\tt com},r}).$

Therefore, the lower bounds derived in Chapter 1 derived for almost surely
bounded oracles still hold for mean square bounded oracles. Although, we still
derive another lower for mean square bounded oracle to point out the
limitations of specific quantization procedures in Section 5.

#####  2 Structure of our protocols

It will be instructive to recall the definition of the quantizer, since the
the outputs of the oracle are passed through a quantizer. An $r$-bit quantizer
consists of randomized mappings333We can use public randomness $U$ for
randomizing. $(Q^{{\tt e}},Q^{{\tt d}})$ with the encoder mapping $Q^{{\tt
e}}:\mathbb{R}^{d}\to\\{0,1\\}^{r}$ and the decoder mapping $Q^{{\tt
d}}:\\{0,1\\}^{r}\to\mathbb{R}^{d}$. The overall quantizer is given by the
composition mapping $Q=Q^{{\tt d}}\circ Q^{{\tt e}}$.

In both this Chapter and the next Chapter, we restrict to memoryless
quantization schemes where the same quantizer will be applied to each new
gradient vector, without using any information from the previous updates.
Specifically, at each instant $t$ and for any precision $r$, the quantizers in
$\mathcal{W}_{r}$ do not use any information from the previous time instants
to quantize the subgradient outputted by $O$ at $t$. Our primary motivation