# Privacy and Anonymity

Adrian Yanes  Aalto University - School of Electrical Engineering
Department of Communications and Networking (ComNet)
Challenged Networks S-38.3455 P
<EMAIL_ADDRESS>
###### Abstract

Since the beginning of the digital area, privacy and anonymity have been
impacted drastically (both, positively and negatively), by the different
technologies developed for communications purposes. The broad possibilities
that the Internet offers since its conception, makes it a mandatory target for
those entities that are aiming to know and control the different channels of
communication and the information that flows through.
In this paper, we address the current threats against privacy and anonymity on
the Internet, together with the methods applied against them. In addition, we
enumerate the publicly known entities behind those threats and their
motivations. Finally, we analyze the state of the art concerning the
protection of the privacy and anonymity on the Internet; introducing future
lines of research.

##  I Introduction

Despite the familiarity of the concepts, privacy and anonymity are commonly
misunderstood within the digital context. In this paper, we refer to these
concepts as foundations of the Common Criteria for Information Technology
Security Evaluation (CC) standard [13]. Therefore, we strictly refer to the
implications of these concepts within the technological jargon, with a deep
emphasis on the Internet. We make the following contributions:

  1. 1.

We provide a precise definition of the research terms, privacy and anonymity,
and their implications.

  2. 2.

We analyze the main threats against privacy and anonymity and their
originators.

  3. 3.

We share a resume of the state of art in terms of the protection of the
privacy and anonymity on the Internet.

The remainder of the paper is organized as follows. In Section 2 we analyse
the main threats against privacy and anonymity and their originators. In
Section 3, we show the current methodologies applied to gain control over the
privacy and anonymity of the users. We enumerate the current technologies
available to protect privacy and anonymity on the Internet in Section 4. In
Section 5 we introduce the proposed improvements over the state of the art. We
present our conclusions in Section 6.

###  I-A Privacy

In the past few decades there have been several debates about the precise
definition of privacy. The Universal Declaration of Human Rights [12] in both
article 12 and 19, references the concept as a human right:

Article 12: No one shall be subjected to arbitrary interference with his
privacy, family, home or correspondence, nor to attacks upon his honour and
reputation […]

Article 19: Everyone has the right to freedom of opinion and expression; this
right includes freedom to hold opinions without interference and to seek,
receive and impart information and ideas through any media and regardless of
frontiers.

Other authors refer to privacy as “the claim of individuals, groups, or
institutions to determine for themselves when, how, and to what extent
information about them is communicated to others.” [25]

According with the CC standard [13], privacy involves “user protection against
discovery and misuse of identity by other users”. In addition, the CC standard
[13] defines the following requirements in order to guarantee privacy:

  * •

Anonymity

  * •

Pseudonymity

  * •

Unlinkability

  * •

Unobservability

Thus, we consider the definition of privacy as a framework of requirements
that prevents the discovery and identity of the user.

###  I-B Anonymity

As stated before, anonymity is intrinsically present in the concept of
privacy. Nevertheless, anonymity refers exclusively to the matters related to
the identity. The CC standard [13] defines “[anonymity] ensures that a user
may use a resource or service without disclosing the user’s identity. The
requirements for anonymity provide protection of the user identity. Anonymity
is not intended to protect the subject identity. […] Anonymity requires that
other users or subjects are unable to determine the identity of a user bound
to a subject or operation.” [13] [21]

Accordingly, we consider the definition of anonymity as the property that
guarantees user’s identity from being disclosed without consent.

###  I-C Other concepts involved in privacy & anonymity

####  I-C1 Pseudonymity

Notwithstanding, the use of anonymity techniques can protect the user from
revealing their real identity. Most of the time there is a technological
requirement necessary to interact with an entity, thus, such entity requires
to have some kind of identity. The CC [13] claims [pseudonymity] ensures that
a user may use a resource or service without disclosing its user identity, but
can still be accountable for that use.

####  I-C2 Unlinkability

In order to guarantee a protection of the user’s identity, there is a need for
unlinkability of the user’s activities within a particular context. This
involves the lack of information to distinguish if the activities performed by
the user are related or not.

####  I-C3 Unobservability

The CC standard [13] refers to this concept as “[unobservability], requires
that users and/or subjects cannot determine whether an operation is being
performed.”. Other authors claim that unobservability should be differentiated
from the undetectability [21]. The reasoning behind this, claims that
something can be unobservable, but can still be detected. In this paper we
refer to unobservability as the property that guarantees the impossibility to
distinguish if something exists or not.

##  II Background

Historically, the control of the communications and the flow of information,
are mandatory for any entity that aims to gain certain control over the
society. There are multiple entities with such interests: governments,
companies, independent individuals, etc. Most of the research available on the
topic claims that the main originators of the threats against privacy and
anonymity are governmental institutions and big corporations[16]. The
motivations behind these threats are varied. Nevertheless, they can be
classified under four categories: social, political, technological and
economical. Despite the relation between them, the four categories have
different backgrounds.

###  II-A Social & political motivations

The core of human interaction is communication in any form. The Internet has
deeply impacted in how social interaction is conducted these days. The
popularity and facilities that the Internet offers, makes it a fundamental
asset for the society. Currently, it is estimated that there are more than 2.7
billion individuals users of the Internet in the world[24].

Figure 1:  460 Million IPv4 addresses on world map (2012)[5]

Any entity that gains any level of control over this massive exchange of
information, implicitly obtains two main advantages: the capability to observe
the social interaction without being noticed (hence, being able to act with
certain prediction), and the possibility to influence it. Privacy and
anonymity are the core values against these actions. Nevertheless, several
authoritarian regimes implemented diverse mechanisms for the dismissal of
both, privacy and anonymity.

Many of the authors highlight that the foundations of these threats are most
often motivated for ideological reasons[16], thus, in countries in which free
of speech or political freedom are limited, privacy and anonymity are
considered an enemy of the state. In addition, national defense and social
“morality” are also some of the main arguments utilized when justifying
actions against privacy and anonymity[8].

According to the OpenNet Initiative[1], there are at least 61 countries that
have implemented some kind of mechanism that negatively affects privacy and
anonymity. Examples of these countries are well-known worldwide: China[26],
Iran[2], North Korea and Syria, among others. In addition, recent media
revelations111Global surveillance programs: PRISM(UK), Tempora(NSA), Muscular
(NSA) shown that several mechanisms that are negatively affecting privacy and
anonymity have been implemented in regions such as the U.S. and Europe.

###  II-B Technological issues

There are some cases in which the threats against privacy and anonymity occur
due to the lack of proper technology. Sometimes these threats can occur
unintentionally. An example of this are bugs in software that are not
discovered and somehow reveal information about the identity or data of the
users. Also, misconfigured Internet services that do not use proper encryption
and identity mechanisms when offering interaction with their users. Certain
techniques utilized by the ISPs can lead to situations in which the user’s
data and identity gets compromised even if the ISPs’ intentions are focused on
bandwidth optimization. Finally, non-technological educated users can be a
threat to themselves by unaware leaking their identity and data voluntarily
but unaware of the repercussions (e.g. usage of social networks, forums,
chats, etc).

###  II-C Economical motivations

As stated previously, the impact and penetration of the Internet in modern
society affects almost every aspect of it, with a primary use of it for
commercial/industrial purposes. There are multiple economical interests that
are related directly to the privacy and anonymity of the users. Several
companies with Internet presence take advantage of user’s identity in order to
build more successful products or to target a more receptive audience. Lately,
the commercialization of user’s data has proven to be a profitable business
for those entities that have the capability of collecting more information
about user’s behavior. In addition, due to the popularity of Internet for
banking purposes, the privacy and anonymity of the users are a common target
for malicious attackers seeking to gain control over user’s economical assets.

##  III Mechanisms used to interfere privacy and anonymity

In the past few decades, a big technological and economical investment has
been made by some entities seeking to gain some control over the privacy and
anonymity on the Internet. Nevertheless, there are not too many commercial
technologies developed with this particular purpose[16]; forcing the
development of custom solutions adapted to the particular use case/target.
Depending of the originator, the technology utilized can have different types
of targets, the most common being nodes and individual users on the Internet.
The categorization of the technology falls in two areas: hardware and software
solutions. The devices utilized for these targets are commonly denominated
Deep Packet Inspection (DPI) devices. Their main use is the classification of
the network traffic, together with the inspection of packet headers and
payloads. Note that most of these devices are not manufactured to directly
target the privacy and anonymity of the users. Instead, they have a generalist
purpose (commonly associated to routing and QoS purposes). Nevertheless, these
devices can be configured in ways that the privacy and anonymity get affected.

We will analyze the different threats using the OSI model[7] as reference,
highlighting the most common compromises on terms of privacy and anonymity
across the different layers.

###  III-A Physical Layer

Any possible threat on the physical layer implies direct access to the
hardware involved in the network. Most common artifacts utilized are known as
network taps: devices that provide access to the data flow of the network once
they are attached to it. These devices can be used either to monitor the
network silently (sniffing) or to redirect the full traffic of the network to
a different node. Implicitly, any observation of the network traffic involves
the possibility of affecting the privacy and anonymity of the traffic.

###  III-B Data link layer

Most of the hardware solutions targeting the data link layer focus on the
media access control (MAC) sublayer. It is in the MAC sublayer that certain
filters can be implemented. The addressing of the destinations occurs in this
layer, which are unique. This is the first control point for those entities
that are aiming to obtain some information concerning user’s identity, data
flows and destinations. Note, the property of uniqueness of the MAC address
and the current standard 222Referring here to the assignation of MAC address
schemes by manufacturer, allows the categorization of the devices present in
the network. This can lead to a premature identification of the user (by
manufacturer/model).

###  III-C Network layer

Due to the nature of the Internet protocol suite, and the use of Internet
Protocol (IP) as its core; the network layer plays a crucial role while
interfering with the privacy and anonymity of the network traffic. Most of the
DPI hardware focused on the network layer targets the inspection of the IP
packets. The IP packets contain all of the relevant information required for
routing purposes. Therefore, it is a mandatory target when aiming to reveal
the identities of the users. The analysis is performed mainly on the IP
header; more specifically, on the source address, destination address and
protocol type. This data can be utilized with different malicious purposes;
the analysis and processing of IP headers can lead to the direct
identification of the user involved in the communication.

Figure 2: IPv4 header fields commonly targeted (red)

Furthermore, statistical analysis can be performed to determine the population
of users even if they are using encrypted protocols over the IP[6]. Finally,
the identification of the protocol utilized, provides enough information to
perform further analysis of the data that the IP packet is transporting. This
makes the network layer a critical asset for inspecting the network traffic.
It is in this layer where some of the entities previously mentioned implement
heavy traffic analysis and/or filtering.

###  III-D Transport layer

The Transport Control Protocol (TCP) is the most popular protocol on the
transport layer on the Internet protocol suite. There is an agreed assumption
that TCP remains to be the main transport protocol on the Internet, thus it is
the most targeted when interfering with the privacy and anonymity of the
users. A TCP header contains (among other data) the source port and
destination port. This information makes it possible to identify (in most
cases) what type of application is being used over TCP; therefore allowing it
to determine the kind of inspection required to capture the data transmitted
in the TCP segment.

Despite, the fact that some applications can use TCP ports out of range of
well-known ports, most of the Internet traffic is based on protocols such as
HTTP, SMTP, POP3, IMAP, etc; for which TCP ports and protocol states are
easily recognized while using DPI techniques/solutions. Therefore, this
facilitates the task of targeting a particular network traffic and its
processing for further analysis. The biggest concerns, in terms of privacy and
anonymity, is that the current technology allows inspection of every single
TCP segment and its content. Despite encryption gaining in popularity, in both
the implementation of application protocols and as user practice, most of the
Internet traffic is still unencrypted. Hence, any traffic analysis that is
performed over the transport layer on unencrypted data reveals the content of
the transmission, thus, eliminating any kind of privacy.

In addition, due to TCP’s architecture, the inspection realized over the data
flows is granular and accurate, mainly due to the possibility to identify
sources and destinations, together with the content of the payload. There is
still a possibility in which the transport layer gets compromised but not the
identity of the source and destinatary. Nevertheless, an observer can gather
enough information to conclude over time, the final identity of the parties
involved, in the case that the payload contains sensitive data about their
identity.

###  III-E Application Layer

The DPI solutions utilized over the application layer are varied, and
sometimes protocol specific[16]. DPI techniques/technologies focused on the
application layer provide the possibility to capture and recompose the data of
the transmission. This generates high-risk threats of the privacy and
anonymity of the users exposing the data of a particular application that the
user is using. Examples include the indiscriminate analysis of the web traffic
that some entities are performing[16]; resulting in the compilation of user
profiles, type of content visiting, frequency, location, etc. The possibility
to cross-reference the analysis of different application protocols utilized
for the same user; building user profiles that contain all kinds of personal
and behavioral information that gets stored and categorized without the user’s
consent.

Due to the fact that it is in this layer where the data gets originated, other
techniques get in place that can affect the privacy and anonymity. Other
popular protocols such as those dedicated to e-mail, are common targets due to
the sensibility of information that they usually transmit. In this case, the
threats against privacy and anonymity does not necessarily happen in the
transmission, but in the software itself. Certain entities have implemented
control mechanisms over the software utilized to handle e-mail, such as
desktop clients and webmails.

Several applications make heavy use of encryption techniques in order to
secure the communication on the layers below. Nevertheless, there is a
possibility that the methods utilized by the application protocol to encrypt
the communication are being compromised even before the transmission begins.
Examples of this include possible backdoors recently claimed[23] on some of
the cryptographically secure pseudo-random number generators (CSPRNG) utilized
to generate encryption keys. If this is the case, certain entities could
decrypt traffic that is thought to be secure by the users, leading again to an
attack of their privacy and anonymity, even when the users think they are
using proper mechanisms to protect themselves. These recent events open
several questions about how reliable a protocol can be if the cryptographic
assumptions utilized are somewhat misleading.

##  IV Mechanism to enforce better privacy and anonymity

In the previous section we enumerate the different technologies utilized in
order to establish certain controls over the privacy and anonymity of the
users. As it is common when any mechanism of oppression is enforced, several
alternatives are created in order to avoid those mechanisms. Privacy and
anonymity have been a big concern since the beginning of the Internet. In
addition to those entities that are aiming to establish the above mentioned
controls, there are also several companies, organizations and individuals,
that are spending time and resources developing mechanisms of defense against
the mentioned threats. We introduce the state of art concerning the
enforcement of privacy and anonymity on the Internet.

###  IV-A Technological principles behind the privacy and anonymity

The majority of the techniques utilized to guarantee privacy are related to a
combination of encryption and anonymity techniques. The vast majority of
anonymity techniques rely on protecting the real identity through a
combination of methods that are difficult to trace the origin and destination
of the communication channel. Despite the complexity that encryption
mechanisms can involve, most of the modern and popular application protocols
provide the possibility to establish the connection through secure channels;
either through the use of the Transport Secure Layer (TLS), or through the
configuration of proxies or socket secure (SOCKS) mechanisms.

There are certain methods to measure the grade of privacy and anonymity. The
degree of privacy is mostly linked to the type of encryption utilized and
computational capacity available. Different encryption algorithms are
currently available, offering certain guarantees for the users. Several
protocols in the application layer rely on these algorithms as the core of
privacy enforcement. Some examples of this is the use of public-key
cryptography[4] and the use of algorithms such as RSA[14] and DSA[20]. In
addition, and due to recent media revelations, some applications are moving to
new cryptography schemes based on the use of elliptic curve cryptography such
as Elliptic Curve Diffie-Hellman (ECDH), Integrated Encryption Scheme (IES) or
Elliptic Curve Digital Signature Algorithm (ECDSA). The main argument behind
the use of new cryptography schemes, is the suspected evidences concerning the
pseudo-random number generators utilized for them, and the possibility of
broken cryptography[23]. Furthermore, the possibility to encapsulate the
connections through a SOCKS interface allows the use of routing techniques
through anonymous networks, that are difficult to trace.

###  IV-B Proxy server

One of the oldest technologies used to enforce privacy and anonymity has been
the use of proxy servers. Perhaps due to the simplicity in their functioning,
together with their popularity in the early days of the Internet, proxy
servers still are one of the main technologies in use when enforcing privacy
and anonymity. The function of a proxy server consists mainly in masking the
client requests, providing a new identity, i.e. a different IP address
possibly located in a different geographical location. There is a vast number
of proxy servers publicly and privately currently available such as
www.anonymizer.ru, provides integrated proxy solutions within the web browser.
In addition, several lists of free proxies are published daily across the
Internet333anonymousproxylists.net, fresh-proxy-list.net, free-proxy-server-
list.com, freeproxy.ru, nntime.com, etc, offering all kind of proxies located
in different countries, with different levels of anonymity. Notwithstanding,
proxys servers cannot be considered a reliable method to guarantee privacy and
anonymity by definition. The main reason being that the proxy server knows the
origin and destination of the requests, therefore, if it is compromised, it
can expose the identity of the users behind its use[17]. Also, although the
proxy server can keep the identity secret, there is no guarantee that the
content of the requests is not being monitored. Therefore, proxy servers
cannot guarantee any property related to plausible deniability and true
anonymity/privacy, thus they should be avoided as method to guarantee privacy
and anonymity as defined in this paper.

###  IV-C Onion routing

Onion Routing is a general purpose infrastructure for private communication
over a public network[10]. The core architecture of onion routing is the
implementation of mixed networks, i.e. nodes that are accepting messages from
different sources and routing them randomly to other nodes within the network.
The messages transmitted between them are encrypted, and different layers of
encryption get removed in the process of routing while traveling across the
nodes[10]. This increases the difficulty of monitoring the traffic (thus
revealing the identity). In addition, onion routing is not node-dependent,
therefore, the compromising of a router does not compromise the network itself
(although can facilitate the traffic analysis). Nevertheless, onion routing
has some weaknesses while protecting the privacy and anonymity of its users.

Recent research[6] shows that even if the traffic is encrypted and hard-
traceable, there are still possibilities to conclude the population of users
and their geographical location. Furthermore, intersection attacks and timing
analysis[22], can reveal user’s behavior within the onion routing network,
leading to further identification of the sources or destinations. Despite
these issues, onion routing is still considered one of the best alternatives
when aiming to guarantee privacy and anonymity.

###  IV-D TOR

TOR, previously known as The Onion Router[9], is among the most popular
solutions used these days to protect privacy and anonymity on the Internet.
The main goal of TOR it is to provide a circuit-based low-latency anonymous
communication service[9].TOR’s core architecture is based on the same
principles as onion routing. TOR contains several improvements over
traditional onion routing, including: “perfect forward secrecy, congestion
control, directory servers, integrity checking, configurable exit policies,
and a practical design for location-hidden services via rendezvous points”[9].
Some nodes within the TOR network act as discovery servers, providing
“trusted” known routers, that are available for the end users. TOR routers
have different roles and they can be classified as:

  * •

Middle-relay: receive traffic and passes it to another relay

  * •

Bridges: publicly listed and their main goal is to provide an entry point on
networks under heavy surveillance and censorship

  * •

Exit-relay: the final relay before reaching the destination and are publicly
advertised

Figure 3: TOR functioning. (Source: EFF)

TOR has won popularity across the most common Internet users. The main reason
(in addition to its enforcement of privacy and anonymity) is due to the fact
that the it is free-software and there are multiple cross-platform clients
available. In addition, several extensions/add-ons are available for the most
popular web-browsers, making TOR a very suitable solution. In addition,
because TOR is configurable in most of the applications through a SOCK
interface, TOR can be used for a broad number of protocols, facilitating
anonymity in different type of services[9].

The success of TOR does not rely only on its core technology and principles,
but on the network of volunteers that maintain the nodes. Due to TOR’s design,
anyone with enough bandwidth can provide a new router, allowing this to expand
TOR worldwide. Nowadays, TOR network is composed of more than 5000 routers.

Figure 4: TOR relays & bridges available

Furthermore, TOR user’s population has been fluctuating over time. Recent
media revelations concerning global surveillance programs, allowing TOR to win
even more popularity across common users, making the network grow
considerable, both on relays and users, in the past months, reaching peaks of
more than 5 million daily connections to the network.

Figure 5: TOR user population

Despite its popularity, TOR is subjected to a certain degree of the techniques
mentioned in Section 3. TOR architecture does not prevent statistical analysis
over its traffic. Some authors highlight the possibility to interfere in nodes
with high traffic, being able to perform traffic analysis with enough accuracy
that can affect the anonymity of the network[19]. In addition, and due to the
publicity of the exit-relays, these particular nodes can be targeted either
for traffic interception or Denial of Service attacks (DoS), affecting the
functionality of the network. Finally, TOR relay advertisement leads to the
generation of blacklists by ISPs and governmental organizations that are
aiming to control mechanisms enforcing privacy and anonymity, making it
difficult for the end users to use TOR. In Section 5 we introduce the possible
improvements to do in order to comply with the definitions stated in this
paper.

##  V Related work and future improvements

In the previous sections, we have analyzed the different motivations,
technologies and state of the art concerning the threats and enforcement of
privacy and anonymity on the Internet. All of the research available these
days focuses mainly on two aspects related to privacy and anonymity: how to
obtain secure and trustable encryption methods, and how to guarantee, real
anonymous communications.

As of today, there is still no single solution available that is complaint
with the definitions of privacy and anonymity introduced in Section 1.
Nowadays, every communication done through the Internet that aims to be
private and anonymous requires the use of cryptography and hard-trace routing
techniques. Proxies and TOR are among the most used anonymity technologies[17]
and public-key cryptography is the most popular method aiming for privacy.
Nevertheless, it is still possible to perform different attacks over these
techniques, leading always to some result that invalidate the required
properties for privacy and anonymity mentioned in Section 1. We introduce some
of the possible improvements that current lines of research are proposing in
order to enforce better privacy and anonymity.

###  V-A Possible solutions for traffic analysis

Traffic analysis (both active and passive), is one of the primary techniques
when targeting networks such as TOR. Recent research suggests that one way to
achieve better privacy and anonymity over this kind of networks, will be the
generation of random connections to achieve better plausible deniability[6].
In addition, there are some proposals to obfuscate TOR’s traffic, adding
delays or artificial traffic, together with package batching techniques[15].
Theoretically, these two improvements, will guarantee true anonymity by making
the traffic analysis hard-computable. Nevertheless, there is no empirical
evidence yet, mainly because they have not been implemented within the
production network (i.e. with a real population of users).

###  V-B Blacklisting techniques

Both proxy servers and TOR routers are suffering blacklisting techniques.
Because the implicit principles of both technologies (available public nodes),
it will require a modification of how they are used and discovered, in order
to avoid blacklisting. The main proposals aim for using a rendezvous protocol
as the only way to distribute the address of the nodes[18]

###  V-C Better encryption methods

There is a common effort within the cryptography community, to provide more
robust and reliable encryption schemes. In the last year, there has been new
contributions related to Elliptic curve cryptography, specially those not
linked to any corporation or standardization organization such as the
Curve25519[3]. It is expected that several well known protocols will start
using these new cryptography schemes, thus avoiding the possible backdoors
established in the current/popular schemes utilized.

###  V-D ISP cooperation

It has been highlighted by some authors[11], that ISPs are playing a crucial
role in privacy and anonymity matters. They are the main entities responsible
for implanting mechanisms that can affect the privacy and anonymity of the
users. Nevertheless, there are not too many “friendly” ISPs in these matters.
Some proposals involve the commitment of the ISP to provide better quality
relay-bridges for TOR[11]. Also, there have been official requests to get more
neutrality and protection from the ISPs. Nevertheless, all of them are still
subjected to the laws that sometimes conflict with the mechanisms for
guaranteeing privacy and anonymity.

##  VI Conclusion

In this paper we introduced the definitions of privacy and anonymity according
to the latest related standards of the field. We analyzed the main originators
behind the threats against the privacy and anonymity on the Internet; we
enumerate their motivations, together with the techniques and technologies
utilized to control the privacy and anonymity on the Internet. In addition, we
gave an overview of the state of the art concerning the enforcement of privacy
and anonymity on the Internet, enumerating the most common technologies by the
users, together with their shortcomings. Finally, we introduced the new lines
of research together with their proposals. We conclude that there is not yet
available any method that guarantees real privacy and true anonymity.

The author considers that despite the reasons given by governments and
corporations, privacy and anonymity are a human right that must be preserved
no matter the channel of communication used. It is a moral responsibility for
the scientific community to research, develop and implement better
technologies to guarantee our fundamental rights.

## References

  * [1] Opennet initiative.  2013\.
  * [2] Simurgh Aryan, Homa Aryan, and J. Alex Halderman.  Internet Censorship in Iran: A First Look.  In Free and Open Communications on the Internet, Washington, DC, USA, 2013. USENIX Association.
  * [3] Daniel J. Bernstein.  Curve25519: New diffie-hellman speed records.  In Public Key Cryptography - PKC 2006, 9th International Conference on Theory and Practice of Public-Key Cryptography, volume 3958 of Lecture Notes in Computer Science, pages 207–228. Springer, 2006.
  * [4] J. Callas, L. Donnerhacke, H. Finney, D. Shaw, and R. Thayer.  OpenPGP Message Format.  RFC 4880 (Proposed Standard), November 2007.  Updated by RFC 5581.
  * [5] Carna Botnet.  Internet census 2012 — port scanning /0 using insecure embedded devices, March 2013.
  * [6] D. Choffnes, J. Duch, D. Malmgren, R. Guiermá, F. E. Bustamante, and L. Amaral.  Swarmscreen: Privacy through plausible deniability in p2p systems.  Technical report, Northwestern University, March 2009.
  * [7] J. D. Day and H. Zimmermann.  The OSI reference model.  Proceedings of the IEEE, 71(12):1334–1340, December 1983.
  * [8] Ronald J. Deibert, John G. Palfrey, Rafal Rohozinski, and Jonathan Zittrain.  Access denied: The practice and policy of global internet filtering.  2008\.
  * [9] Roger Dingledine, Nick Mathewson, and Paul Syverson.  Tor: The second-generation onion router.  In In Proceedings of the 13th USENIX Security Symposium, pages 303–320, 2004.
  * [10] David Goldschlag, Michael Reed, and Paul Syverson.  Onion routing for anonymous and private internet connections.  Communications of the ACM, 42:39–41, 1999.
  * [11] Amir Houmansadr, Giang T.K. Nguyen, Matthew Caesar, and Nikita Borisov.  Cirripede: Circumvention infrastructure using router redirection with plausible deniability.  In Proceedings of the 18th ACM Conference on Computer and Communications Security, CCS ’11, pages 187–200, New York, NY, USA, 2011. ACM.
  * [12] United Nations international community.  The universal declaration of human rights.  1948\.
  * [13] Information technology — Security techniques — Evaluation criteria for IT security, 2005.
  * [14] J. Jonsson and B. Kaliski.  Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1.  RFC 3447 (Informational), February 2003.
  * [15] Stevens Le-Blond, David R. Choffnes, Wenxuan Zhou, Peter Druschel, Hitesh Ballani, and Paul Francis.  Towards efficient traffic-analysis resistant anonymity networks.  In SIGCOMM, pages 303–314, 2013.
  * [16] Christopher S. Leberknight, Mung Chiang, and Felix Ming Fai Wong.  A taxonomy of censors and anti-censors: Part i-impacts of internet censorship.  IJEP, 3(2):52–64, 2012.
  * [17] Bingdong Li, Esra Erdin, Mehmet H. Gunes, George Bebis, and Todd Shipley.  An overview of anonymity technology usage.  Computer Communications, 36(12):1269–1283, July 2013.
  * [18] Patrick Lincoln, Ian Mason, Phillip Porras, Vinod Yegneswaran, Zachary Weinberg, Jeroen Massar, William Simpson, Paul Vixie, and Dan Boneh.  Bootstrapping Communications into an Anti-Censorship System.  In Free and Open Communications on the Internet, Bellevue, WA, USA, 2012. USENIX Association.
  * [19] Steven J. Murdoch and George Danezis.  Low-cost traffic analysis of tor.  In Proceedings of the 2005 IEEE Symposium on Security and Privacy, SP ’05, pages 183–195, Washington, DC, USA, 2005. IEEE Computer Society.
  * [20] National Institute of Standards and Technology.  FIPS PUB 180-1: Secure Hash Standard.  April 1995.  Supersedes FIPS PUB 180 1993 May 11.
  * [21] Andreas Pfitzmann and Marit Hansen.  A terminology for talking about privacy by data minimization: Anonymity, unlinkability, undetectability, unobservability, pseudonymity, and identity management.  http://dud.inf.tu-dresden.de/literatur/Anon_Terminology_v0.34.pdf, August 2010.  v0.34.
  * [22] Vitaly Shmatikov and Ming-Hsiu Wang.  Timing analysis in low-latency mix networks: attacks and defenses.  In IN: PROCEEDINGS OF ESORICS, pages 18–33, 2006.
  * [23] D. Shumow and N. Ferguson.  On the possibility of a back door in the NIST SP800-90 dual Ec prng.  2007\.
  * [24] International Telecommunication Union.  World telecommunication/ict indicators database, dec 2013.
  * [25] A.F. Westin.  Privacy and Freedom.  Bodley Head, 1970.
  * [26] Philipp Winter and Jedidiah R. Crandall.  The great firewall of china : How it blocks tor and why it is hard to pinpoint.  ;login:, 37(6):42–50, 2012.


Finally, by (4.18), we have $\frac{1}{\alpha_{t}}-\frac{1}{\alpha_{t-1}}=1$
for every $t\in S$. Combining everything gives

$\displaystyle\sum_{t\leq
n}\frac{1}{\alpha_{t}}-\frac{1}{\alpha_{t-1}}\lesssim
d_{n}\log\left(dN\right)+|S|\lesssim d_{n}\log\left(dN\right),$

thereby concluding the proof of 3. ∎

##  5 Forming Small Coresets for Convex Bodies (Proof of Theorem 4)

In this section, we prove Theorem 4. See Algorithm 5.1.

Algorithm 5.1 Streaming coreset for convex hull

1:Input: Stream of points $\bm{z}_{t}$; Update rule for Algorithm 4.4
$\mathcal{A}$.

2:Output: Set $S\subseteq[n]$.

3:for $t=1,\dots,n$ do

4: Receive $\bm{z}_{t}$.

5: Let
$\mathcal{E}_{\mathsf{test}}=\mathcal{A}(\bm{c}_{t-1},\mathcal{E}_{t-1},\bm{z}_{t})$.

6: Let
$d_{t}=\mathsf{dim}\left(\mathsf{aff}\left(\bm{z}_{1}-\bm{c}_{t-1},\dots,\bm{z}_{t}-\bm{c}_{t-1}\right)\right)$.

7: if $d_{t}>d_{t-1}$ or
$\frac{\mathsf{Vol}_{d_{t}}(\mathcal{E}_{\mathsf{test}})}{\mathsf{Vol}_{d_{t}}(\mathcal{E}_{t-1})}\geq
e$ then

8: Let
$\bm{c}_{t},\mathcal{E}_{t}=\mathcal{A}(\bm{c}_{t-1},\mathcal{E}_{t-1},\bm{z}_{t})$.

9: Update $S_{t}=S_{t-1}\cup\left\\{\bm{z}_{t}\right\\}$.

10: else

11: Let $\bm{c}_{t},\mathcal{E}_{t}=\bm{c}_{t-1},\mathcal{E}_{t-1}$.

12: Let $S_{t-1}=S_{t}$.

13:Output: $S_{n}$

For a sketch of the intuition and the argument we will use for the proof, see
Section 2.3.

###### Proof of Theorem 4.

We prove two properties of Algorithm 5.1. First, we show $\left\lvert
S_{t}\right\rvert\leq
O\left(d_{t}\cdot\log\left(d_{t}\cdot\max_{t^{\prime}\leq
t}\nicefrac{{R_{t}}}{{r_{t^{\prime}}}}\right)\right)$ and, further,
$\left\lvert S_{t}\right\rvert\leq
O\left(d_{t}\cdot\log\left(dN\right)\right)$ if points $\bm{z}_{t}$ have
integer coordinates between $-N$ and $N$. Second, we show that
$\mathsf{conv}\left(Z|_{S_{t}}\right)\subseteq\mathsf{conv}\left(Z|_{[t]}\right)\subseteq
O\left(d_{t}\cdot\log\left(d_{t}\cdot\max_{t^{\prime}\leq
t}\nicefrac{{R_{t}}}{{r_{t^{\prime}}}}\right)\right)\cdot\mathsf{conv}\left(Z|_{S_{t}}\right)$
and
$\mathsf{conv}\left(Z|_{S_{t}}\right)\subseteq\mathsf{conv}\left(Z|_{[t]}\right)\subseteq
O\left(d_{t}\cdot\log\left(dN\right)\right)\cdot\mathsf{conv}\left(Z|_{S_{t}}\right)$.

##### Bounding $\left\lvert S_{t}\right\rvert$.

It is enough to count the number of steps $t$ for which we have
$\frac{\mathsf{Vol}_{d_{t}}(\mathcal{E}_{\mathsf{test}})}{\mathsf{Vol}_{d_{t}}(\mathcal{E}_{t-1})}\geq
e$.

It is easy to see that for all $t$, we have
$r(Z|_{[t]})\cdot\left(B_{2}^{d}\cap\mathsf{aff}\left(\bm{z}_{1}-\bm{c}_{t},\dots,\bm{z}_{t}-\bm{c}_{t}\right)\right)\subseteq\bm{c}_{t}+\mathcal{E}_{t}$.
Additionally, by the definition of $R(Z)$, we always have $Z|_{[t]}\subseteq
R(Z)\cdot\left(B_{2}^{d}\cap\mathsf{aff}\left(\bm{z}_{1}-\bm{c}_{t},\dots,\bm{z}_{t}-\bm{c}_{t}\right)\right)$.
These are enough to give volume lower and upper bounds in each step. Next, for
each step in which we add an element to $S_{t-1}$ to obtain $S_{t}$, the
volume must increase by a factor of $e$. It easily follows that the number of
elements in $S_{t}$ satisfies

$\displaystyle\left\lvert S_{t}\right\rvert\leq\log\left(\max_{t^{\prime}\leq
t}\frac{\prod_{i=1}^{d_{t}}R(Z|_{[t]})}{\prod_{i=1}^{d_{t}}r(Z|_{[t^{\prime}]})}\right)=d_{t}\log\left(\max_{t^{\prime}\leq
t}\frac{R(Z|_{[t]})}{r(Z|_{[t^{\prime}]})}\right).$

We now give an upper bound for the case when all coordinated of $\bm{z}_{t}$
are integers not exceeding $N$ in absolute value. It is easy to see that the
update rule in Algorithm 5.1 exactly corresponds to the steps where we have

$\displaystyle\frac{1}{\alpha_{t}}-\frac{1}{\alpha_{t-1}}\gtrsim 1,$

and in the same way as in the proof of 3, we have for all $t$ that

$\displaystyle\sum_{t\geq
1}\frac{1}{\alpha_{t}}-\frac{1}{\alpha_{t-1}}\lesssim
d_{t}\log\left(dN\right).$

It therefore follows that $\left\lvert S\right\rvert\lesssim
d_{t}\log\left(dN\right)$, as desired.

##### Bounding the distortion of the chosen points.

Consider some iteration $t^{\prime}\leq t$. Without loss of generality, let
$\bm{c}_{t^{\prime}-1}=0$. Suppose $\bm{z}_{t^{\prime}}$ does not result in an
update to $S_{t^{\prime}-1}$. This implies that $\bm{z}_{t^{\prime}}\in
2e\cdot\mathcal{E}_{t^{\prime}-1}$. Next, observe that
$0\in\bm{c}_{t}+\mathcal{E}_{t}$. Putting these together, we have
$\bm{z}_{t^{\prime}}\in\left(\bm{c}_{t}+\mathcal{E}_{t}\right)+2e\cdot\mathcal{E}_{t^{\prime}-1}$.
Since $\mathcal{A}$ is monotone, we must have
$2e\cdot\mathcal{E}_{t^{\prime}-1}\subseteq\bm{c}_{t}+e\cdot\mathcal{E}_{t}$;
hence, we may write
$\bm{z}_{t^{\prime}}\in\bm{c}_{t}+\left(2e+1\right)\mathcal{E}_{t}$.

The inner ellipsoid $\bm{c}_{t}+\alpha_{t}\cdot\mathcal{E}_{t}$ will still be
an inner ellipsoid for the points determined by $S_{t}$. Stitching together
all our inclusions, we have

$\displaystyle\bm{c}_{t}+\alpha_{t}\cdot\mathcal{E}_{t}\subseteq
Z|_{S_{t}}\subseteq
Z\subseteq\bm{c}_{t}+(2e+1)\mathcal{E}_{t}\subseteq\frac{2e+1}{\alpha_{t}}\cdot
Z|_{S_{t}}.$ (5.1)

which means that

$\displaystyle Z|_{S_{t}}\subseteq Z\subseteq
O\left(d_{t}\cdot\log\left(d_{t}\cdot\max_{t^{\prime}\leq
t}\frac{R(Z|_{([t]\cap S_{t})})}{r(Z|_{([t^{\prime}]\cap
S_{t})})}\right)\right)\cdot Z|_{S_{t}}.$

Notice that this is nearly what we want, except that the aspect ratio term is
in terms of the subset body $Z|_{S_{t}}$. To obtain the final guarantee in
terms of the aspect ratio of $Z|_{[t]}$, observe that the above guarantee
readily implies that

$\displaystyle O\left(d_{t}\cdot\log\left(d_{t}\cdot\max_{t^{\prime}\leq
t}\frac{R(Z|_{([t]\cap S_{t})})}{r(Z|_{([t^{\prime}]\cap
S_{t})})}\right)\right)\leq
O\left(d_{t}\cdot\log\left(d_{t}\cdot\max_{t^{\prime}\leq
t}\frac{R(Z|_{[t]})}{r(Z|_{[t^{\prime}]})}\right)\right).$

We now give the corresponding improvement when the $\bm{z}_{t}$ are integer-
valued. As before, (5.1) holds. From this, we get

$\displaystyle Z|_{S_{t}}\subseteq Z\subseteq
O\left(d_{t}\cdot\log\left(dN\right)\right)\cdot Z|_{S_{t}},$

as desired. This concludes the proof of Theorem 4. ∎

##  6 Lower Bound

In this section, we show 5.

###  6.1 Lower bound adversary

Our proof of 5 constructs an adversary, which given a monotone algorithm
$\mathcal{A}$ and $\kappa\geq 1$, constructs a sequence of points
$\bm{z}_{1},\ldots,\bm{z}_{n}$ satisfying
$\kappa(\mathsf{conv}\left(\bm{z}_{1},\ldots,\bm{z}_{n}\right))\leq\kappa$ to
witness that the algorithm does not produce an approximation better than
$\widetilde{\Omega}(d\log\kappa)$. While by definition $\kappa=\frac{R}{r}$,
our construction keeps $r=1$ (notice that any lower bound construction must be
scale-invariant), and for simplicity we use $R=\kappa$.

Let
$\bm{z}^{\Delta}_{1},\bm{z}^{\Delta}_{2},\ldots,\bm{z}^{\Delta}_{d+1}\in\mathbb{R}^{d}$
be the $d+1$ vertices of a regular simplex $\Delta_{d}$ that circumscribes
$B_{2}^{d}$. Our adversary is described in Algorithm 6.1. It uses a first
phase that feeds $\mathcal{A}$ the vertices of $\Delta_{d}$, then a second
phase that repeatedly feeds $\mathcal{A}$ points at a constant distance from
the previous ellipsoid. Specifically, every new point $\bm{z}_{t}$ in the
second phase is in $\bm{c}_{t-1}+2\cdot\mathcal{E}_{t-1}$, i.e. its distance
is 2 from $\bm{c}_{t-1}$ in the norm that is the gauge of $\mathcal{E}_{t-1}$.

Algorithm 6.1 Lower bound adversary

Input: Monotone algorithm $\mathcal{A}$, $R\geq 1$

1:$(\bm{c}_{0}+\mathcal{E}_{0},\alpha_{0})=(0+B_{2}^{d},1)$ $\triangleright$
Initialize to the unit ball

2:for $t\in\\{1,2,\ldots,d+1\\}$ do $\triangleright$ Phase I: feed
$\mathcal{A}$ the vertices of a simplex

3:
$(\bm{c}_{t}+\mathcal{E}_{t},\alpha_{t})=\mathcal{A}(\bm{c}_{t-1}+\mathcal{E}_{t-1},\alpha_{t-1},\bm{z}^{\Delta}_{t})$

4:$t\leftarrow d+2$

5:while
$\operatorname{\mathsf{vol}}(\mathcal{E}_{t-1})\leq\operatorname{\mathsf{vol}}\left(\frac{R}{2}\cdot
B_{2}^{d}\right)$ do $\triangleright$ Phase II: feed $\mathcal{A}$ points
outside the previous ellipsoid

6: Let $F_{t-1}=\partial(\bm{c}_{t-1}+2\mathcal{E}_{t-1})\cap(R\cdot
B_{2}^{d})$

7: if $F_{t-1}=\varnothing$ then

8: stop

9: Let arbitrary $\bm{z}_{t}\in F_{t-1}$

10:
$(\bm{c}_{t}+\mathcal{E}_{t},\alpha_{t})=\mathcal{A}(\bm{c}_{t-1}+\mathcal{E}_{t-1},\alpha_{t-1},\bm{z}_{t})$

11: $t\leftarrow t+1$

######  Remark 6.1.

This particular construction we give of the hard case is adaptive, meaning
that the adversary’s choice of points depend on the previous ellipsoids the
algorithm outputs. However, this adversary can be made non-adaptive by taking
an $\varepsilon$-net $S$ of $B_{2}^{d}$ for sufficiently small $\varepsilon$,
then feeding $\mathcal{A}$ the sequence of points in sets $S,2\cdot S,4\cdot
S,\ldots,2^{\log_{2}R-1},2^{\log_{2}R}\cdot S$. In consequence, this means
that randomization on the part of the monotone algorithm does not help, unlike
some other online settings.

Let $T$ be the largest value of $t-1$ before the adversary halts. We first
show that the adversary only gives finitely many points before halting.

######  Claim 6.2.

$T\leq O(d\log R)$

###### Proof.

We argue that the volume of $\mathcal{E}_{t}$ increases by at least a constant
factor on each iteration. This is sufficient to bound the number of iterations
by $O(d\log R)$, as $\mathcal{E}_{0}=B_{2}^{d}$, and Line 5 is no longer true
when the volume of $\mathcal{E}_{t}$ exceeds
$\left(\frac{R}{2}\right)^{d}\cdot\operatorname{\mathsf{vol}}(B_{2}^{d})$.

We claim that for all $t\geq d+2$,
$\operatorname{\mathsf{vol}}(\mathcal{E}_{t})\geq\frac{3}{2}\cdot\operatorname{\mathsf{vol}}(\mathcal{E}_{t-1})$.
By applying a nonsingular affine transformation, we can assume without loss of
generality that $\mathcal{E}_{t-1}=B_{2}^{d}$. With a further rotation, we can
assume the newly received point is $\bm{z}_{t}=2\bm{e}_{1}$. From monotonicity
of $\mathcal{A}$ we must have that $\bm{c}_{t}+\mathcal{E}_{t}\supseteq
B_{2}^{d}\cup\\{2\bm{e}_{1}\\}$. Clearly every semi-axis of $\mathcal{E}_{t}$
must have length at least 1 in order to contain $\mathcal{E}_{t-1}$. Observe
that $\mathcal{E}_{t}$ must also contain the segment connecting $-1\bm{e}_{1}$
and $2\bm{e}_{1}$, and so at least one semi-axis must have length at least
$\frac{3}{2}$ (if not, the diameter of $\mathcal{E}_{t}$ would be strictly
less than $3$). Hence as
$\frac{\operatorname{\mathsf{vol}}(\mathcal{E}_{t})}{\operatorname{\mathsf{vol}}(B_{2}^{d})}$
equals the product of the length of the semi-axes of $\mathcal{E}_{t}$, we
have
$\operatorname{\mathsf{vol}}(\mathcal{E}_{t})\geq\frac{3}{2}\operatorname{\mathsf{vol}}(B_{2}^{d})$.
∎

For the analysis we define quantities $A_{t},P_{t}$ associated with the
sequence of ellipsoids for $1\leq t\leq T$:

$A_{t}\coloneqq\frac{1}{\alpha_{t}},\quad
P_{t}\coloneqq\log\left(\frac{\operatorname{\mathsf{vol}}(\mathcal{E}_{t})}{\operatorname{\mathsf{vol}}(B_{2}^{d})}\right)$

By the monotonicity of $\mathcal{A}$, we have that $A_{t}$ and $P_{t}$ are
both nondecreasing in $t$. We first observe that the adversary guarantees that
the final volume of the ellipsoid output by $\mathcal{A}$ is large:

######  Claim 6.3.

At the conclusion of Algorithm 6.1’s execution, we have

$P_{T}\geq d\log\frac{R}{2}$

###### Proof.

There are two ways that the adversary stops: if the condition in Line 5 is no
longer true, or if Line 8 is reached. If the former occurs, then we have
$\operatorname{\mathsf{vol}}(\mathcal{E}_{T})>\operatorname{\mathsf{vol}}(\frac{R}{2}\cdot
B_{2}^{d})$, and clearly then $P_{T}\geq d\log\left(\frac{R}{2}\right)$.

In the latter stopping condition, the algorithm halts at time $T$ when
$\partial(c_{T}+2\mathcal{E}_{T})\cap R\cdot B_{2}^{d}=\varnothing$. The sets
$\partial(c_{T}+2\mathcal{E}_{T})$ and $R\cdot B_{2}^{d}$ can be disjoint in
two cases: $c_{T}+2\mathcal{E}_{T}$ and $R\cdot B_{2}^{d}$ are disjoint; or
$R\cdot B_{2}^{d}\subseteq c_{T}+2\mathcal{E}_{t}$ with the boundaries of both
ellipsoids disjoint. By the monotonicity of $\mathcal{A}$, we have $1\cdot
B_{2}^{d}\subseteq c_{T}+2\mathcal{E}_{T}$, and so eliminate the former case.
But then
$\operatorname{\mathsf{vol}}(2\cdot\mathcal{E}_{T})\geq\operatorname{\mathsf{vol}}(R\cdot
B_{2}^{d})=R^{d}\operatorname{\mathsf{vol}}(B_{2}^{d})$, and taking logarithms
on both sides yields the claim. ∎

Now in contrast to the upper bound where we essentially gave an algorithm for
which $\frac{\Delta A}{\Delta P}$ was upper bounded by a constant, here we
will show a constant lower bound on the same quantity for any monotone
algorithm.

######  Claim 6.4.

There exists a constant $C_{\ref{eqn:lb_step_main}}>0$ such that if $A_{t}\geq
d$, we have

$A_{t+1}-A_{t}\geq C_{\ref{eqn:lb_step_main}}(P_{t+1}-P_{t})$ (6.1)

Observe that this lower bound requires $A_{t}\geq d$, hence necessitating a
first phase using the simplex, whose optimal roundings show tightness for
John’s theorem for general convex bodies. In order to prove the lower bound we
also need a second property, that $A_{t}$ is large compared to $P_{t}$.

######  Claim 6.5.

Let $0\leq\alpha\leq 1,\bm{c}\in\mathbb{R}^{d}$, and $\mathcal{E}$ be an
ellipsoid such that

$\bm{c}+\alpha\cdot\mathcal{E}\subseteq\Delta_{d}\subseteq\bm{c}+\mathcal{E}$

then we have:

  1. 1.

$\alpha\leq\frac{1}{d}$

  2. 2.

$\log\left(\frac{\operatorname{\mathsf{vol}}(\mathcal{E})}{\operatorname{\mathsf{vol}}(B_{2}^{d})}\right)\leq
O\left(\log(d)\cdot\frac{1}{\alpha}\right)$

With the statements of these claims in hand, we are ready to prove the lower
bound.

###### Proof of 5.

It is clear that
$\kappa(\mathsf{conv}\left(\bm{z}_{1},\ldots,\bm{z}_{T})\right)\leq R$, as for
every $1\leq t\leq T$ the adversary guarantees $1\leq\|\bm{z}_{t}\|\leq R$. So
we focus on showing a lower bound on the quality of the approximation produced
by $\mathcal{A}$.

As $\mathcal{A}$ is monotone, after the end of Phase I we must have that

$\bm{c}_{d+1}+\alpha_{d+1}\cdot\mathcal{E}_{d+1}\subseteq\Delta_{d}\subseteq\bm{c}_{d+1}+\mathcal{E}_{d+1}$
(6.2)

Now because $\mathcal{E}_{d+1}$ satisfies the conditions of Claim 6.5, we get
using the definition $A_{d+1}=\frac{1}{\alpha_{d+1}}$ that $A_{t}\geq
A_{d+1}\geq d$ for any $t\geq d+1$. Then we can apply Claim 6.4 for every
$t\geq d+1$ until termination of the algorithm:

$\displaystyle A_{d+2}-A_{d+1}$ $\displaystyle\geq
C_{\ref{eqn:lb_step_main}}\left(P_{d+2}-P_{d+1}\right)$ $\displaystyle
A_{d+3}-A_{d+2}$ $\displaystyle\geq
C_{\ref{eqn:lb_step_main}}\left(P_{d+3}-P_{d+2}\right)$
$\displaystyle~{}\vdots$ $\displaystyle A_{T-1}-A_{T-2}$ $\displaystyle\geq
C_{\ref{eqn:lb_step_main}}\left(P_{T-1}-P_{T-2}\right)$ $\displaystyle
A_{T}-A_{T-1}$ $\displaystyle\geq
C_{\ref{eqn:lb_step_main}}\left(P_{T}-P_{T-1}\right)$

Summing these inequalities, we have

$\displaystyle\sum_{t=d+1}^{T-1}A_{t+1}-A_{t}\geq
C_{\ref{eqn:lb_step_main}}\left(\sum_{t=d+1}^{T-1}P_{t+1}-P_{t}\right)$

Both sides of this inequality are telescoping sums, so simplifying we get

$A_{T}\geq A_{d+1}+C_{\ref{eqn:lb_step_main}}(P_{T}-P_{d+1})$ (6.3)

Again because we can apply Claim 6.5 for $\mathcal{E}_{d+1}$, we have
$P_{d+1}\leq O(\log(d)\cdot A_{d+1})$, which along with (6.3) yields

$A_{T}\geq A_{d+1}+\Omega(P_{T}-\log(d)\cdot
A_{d+1})\geq\Omega(P_{T}-\log(d)\cdot A_{d+1})$

Thus we have

$A_{T}\geq\Omega(\max(A_{d+1},P_{T}-\log(d)\cdot
A_{d+1}))\geq\Omega\left(\frac{P_{T}}{\log(d)}\right)$

and we get the desired bound using Claim 6.3. ∎

Our proof of Claim 6.4 relies on a symmetrization argument to a reduced case
(essentially two-dimensional, like for our algorithms). We now define this
reduced case, and related quantities.

######  Definition 6.6.

In the reduced case, the previous outer and inner ellipsoids are given by
$B_{2}^{d},\alpha\cdot B_{2}^{d}$, and the received point is
$\bm{z}=2\bm{e}_{1}$. The next outer and inner ellipsoids are given by
$c\cdot\bm{e}_{1}+\mathcal{E}_{\mathbf{M}},c\cdot\bm{e}_{1}+\alpha^{\prime}\cdot\mathcal{E}_{\mathbf{M}}$
for $c\in\mathbb{R}$, and
$\mathbf{M}=\mathsf{diag}\left(a,b,b,\ldots,b,b\right)$ for $a,b\geq 1$. We
let $\Delta A=\frac{1}{\alpha^{\prime}}-\frac{1}{\alpha}$ and $\Delta
P=\log\left(\frac{\operatorname{\mathsf{vol}}(\mathcal{E}_{\mathbf{M}})}{\operatorname{\mathsf{vol}}(B_{2}^{d})}\right)$.

Note that the update in this reduced case is monotone if
$B_{2}^{d}\cup\\{2\bm{e}_{1}\\}\subseteq
c\cdot\bm{e}_{1}+\mathcal{E}_{\mathbf{M}}$ and
$c\cdot\bm{e}_{1}+\alpha^{\prime}\cdot\mathcal{E}_{\mathbf{M}}\subseteq\mathsf{conv}\left((\alpha\cdot
B_{2}^{d})\cup\\{2\bm{e}_{1}\\}\right)$.

Now we state the lower bound on $\frac{\Delta A}{\Delta P}$ in this setting,
which is established in Section 6.2. It is exactly the bound of Claim 6.4 in
this special case.

######  Claim 6.7.

In the reduced case, for any monotone update
$c\cdot\bm{e}_{1}+\mathcal{E}_{\mathbf{M}},c\cdot\bm{e}_{1}+\alpha^{\prime}\cdot\mathcal{E}_{\mathbf{M}}$
when $\alpha^{\prime}\leq\frac{1}{d}$ we have

$\frac{\Delta A}{\Delta P}\geq C_{\ref{eqn:lb_step_main}}$ (6.4)

We now give the symmmetrization argument that shows that the above bound in
the special case implies the bound in the general case.

###### Proof of Claim 6.4.

By the monotonicity of $\mathcal{A}$, we have
$(\bm{c}_{t}+\mathcal{E}_{t})\cup\\{\bm{z}_{t+1}\\}\subseteq\bm{c}_{t+1}+\mathcal{E}_{t+1}$
and
$\bm{c}_{t+1}+\alpha_{t+1}\cdot\mathcal{E}_{t+1}\subseteq\mathsf{conv}\left((\bm{c}_{t}+\alpha_{t}\cdot\mathcal{E}_{t})\cup\\{\bm{z}_{t+1}\\}\right)$.
Without loss of generality we assume that
$\bm{c}_{t}+\mathcal{E}_{t}=B_{2}^{d}$ and $\bm{z}_{t+1}=2\cdot\bm{e}_{1}$; we
do this by applying a nonsingular affine transformation that maps $\bm{c}_{t}$
to the origin and $\mathcal{E}_{t}$ to $B_{2}^{d}$, then apply a rotation that
maps $\bm{z}_{t+1}$ to $2\cdot e_{1}$. Let $\bm{c}=\bm{c}_{t+1}$,
$\mathcal{E}=\mathcal{E}_{t+1}$, and $\alpha=\alpha_{t+1}$. Summarizing the
conditions guaranteed by the monotonicity of $\mathcal{A}$, we have that
$B_{2}^{d}\cup\\{2\bm{e}_{1}\\}\subseteq\bm{c}+\mathcal{E}$ and
$\bm{c}+\alpha\cdot\mathcal{E}\subseteq\mathsf{conv}\left((\alpha_{t}\cdot
B_{2}^{d})\cup\\{2\bm{e}_{1}\\}\right)$.

To perform the reduction to the two-dimensional case, we apply a sequence of
volume-preserving symmetrizations to the new inner and outer ellipsoids; these
symmetrizations will also ensure that the update remains monotone. We will
first apply two Steiner symmetrizations. The first of these Steiner
symmetrizations transforms the ellipsoids so that their center lies on the
$\bm{e}_{1}$-axis. The second ensures that the ellipsoids have a semi-axis
that is parallel to $\bm{e}_{1}$. Then, by a final symmetrization step we can
transform the ellipsoids into bodies of revolution about $\bm{e}_{1}$. At that
point it will suffice to consider the two-dimensional reduced case.

Let $\bm{c}^{\prime}$ be the projection of $\bm{c}$ onto the
$\bm{e}_{1}$-axis. The goal of the first symmetrization step is to transform
$\bm{c}+\mathcal{E}$ to $\bm{c}^{\prime}+\mathcal{E}^{\prime}$ so that
$\bm{c}^{\prime}$ lies on the $\bm{e}_{1}$ axis. If $\bm{c}=\bm{c}^{\prime}$
then we do not need to do anything, otherwise we apply Steiner symmmetrization
and consider $S_{\bm{c}-\bm{c}^{\prime}}(\bm{c}+\mathcal{E})$. By Claim 3.4
this is still an ellipsoid, and we also have that the center of
$S_{\bm{c}-\bm{c}^{\prime}}(\bm{c}+\mathcal{E})$ is actually
$\bm{c}^{\prime}$; thus we may write
$S_{\bm{c}-\bm{c}^{\prime}}(\bm{c}+\mathcal{E})=\bm{c}^{\prime}+\mathcal{E}^{\prime}$
for some $\mathcal{E}^{\prime}$. Further, we have that
$S_{\bm{c}-\bm{c}^{\prime}}(\bm{c}+\alpha\cdot\mathcal{E})=\bm{c}^{\prime}+\alpha\cdot\mathcal{E}^{\prime}$,
as the Steiner symmetrization acts similarly on the scaled version of
$\mathcal{E}$. To show that the update is still monotone, we observe that
$\bm{c}^{\prime}+\mathcal{E}^{\prime}=S_{\bm{c}-\bm{c}^{\prime}}(\bm{c}+\mathcal{E})\subseteq
S_{\bm{c}-\bm{c}^{\prime}}(\mathsf{conv}\left((\alpha_{t}\cdot
B_{2}^{d})\cup\\{2\bm{e}_{1}\\}\right))$. But by Claim 3.5 and that
$\bm{c}-\bm{c}^{\prime}\perp\bm{e}_{1}$, $\mathsf{conv}\left((\alpha_{t}\cdot
B_{2}^{d})\cup\\{2\bm{e}_{1}\\}\right)$ is invariant under the symmetrization
$S_{\bm{c}-\bm{c}^{\prime}}$ and so we still have the inclusion
$\bm{c}^{\prime}+\alpha\cdot\mathcal{E}^{\prime}\subseteq\mathsf{conv}\left((\alpha_{t}\cdot
B_{2}^{d})\cup\\{2\bm{e}_{1}\\}\right)$. The ‘outer’ inclusion
$B_{2}^{d}\cup\\{2\bm{e}_{1}\\}\subseteq\bm{c}^{\prime}+\mathcal{E}^{\prime}$
follows in the same way.

We now apply the second and final Steiner symmetrization. Let $\bm{r}$ be the
rightmost point of $\bm{c}^{\prime}+\mathcal{E}^{\prime}$ along $\bm{e}_{1}$;
i.e.
$\bm{r}=\arg\max_{\bm{r}\in\bm{c}^{\prime}+\mathcal{E}^{\prime}}\left\langle\bm{r},\bm{e}_{1}\right\rangle$.
Also let $\bm{r}^{\prime}$ be its projection along the $\bm{e}_{1}$-axis; if
$\bm{r}=\bm{r}^{\prime}$ we again do not need to perform this symmetrization
step, otherwise the Steiner symmetrization we apply is
$S_{\bm{r}-\bm{r}^{\prime}}(\bm{c}^{\prime}+\mathcal{E}^{\prime})$. Since
$\bm{c}^{\prime}$ is at the midpoint of
$\bm{c}^{\prime}+\mathbb{R}(\bm{r}-\bm{r}^{\prime})$ the center of the new
ellipsoid is still $\bm{c}^{\prime}$, so we may write
$S_{\bm{r}-\bm{r}^{\prime}}(\bm{c}^{\prime}+\mathcal{E}^{\prime})=\bm{c}^{\prime}+\mathcal{E}^{\prime\prime}$
and similarly
$S_{\bm{r}-\bm{r}^{\prime}}(\bm{c}^{\prime}+\alpha\cdot\mathcal{E}^{\prime})=\bm{c}^{\prime}+\alpha\cdot\mathcal{E}^{\prime\prime}$.
Like for the previous symmetrization, the fact that
$\bm{r}-\bm{r}^{\prime}\perp\bm{e}_{1}$ means that both inclusions of the
monotone update are preserved. Note finally that $\bm{r}^{\prime}$ is the
rightmost point of $\bm{c}^{\prime}+\mathcal{E}^{\prime\prime}$ and that the
tangent plane of $\bm{c}+\mathcal{E}^{\prime\prime}$ at $\bm{r}^{\prime}$ is
orthogonal to the line segment $\overline{\bm{c}^{\prime}\bm{r}^{\prime}}$, so
$\bm{e}_{1}$ is a semi-axis of $\bm{c}^{\prime}+\mathcal{E}^{\prime\prime}$.

Our last transformation is a symmetrization of a different form, to turn
$\bm{c}^{\prime}+\mathcal{E}^{\prime\prime}$ into a body of revolution. Let
$\sigma_{1}$ be the length of the semi-axis $\bm{e}_{1}$ of
$\mathcal{E}^{\prime\prime}$, and $\sigma_{2},\ldots,\sigma_{d}$ be the
lengths of the other semi-axes of $\mathcal{E}^{\prime\prime}$. We let
$\mathcal{E}^{\prime\prime\prime}$ be the ellipsoid that has a $\bm{e}_{1}$ as
a semi-axis of length $\sigma_{1}$, and where every other semi-axis of
$\mathcal{E}^{\prime\prime\prime}$ has length
$\sigma^{\prime}\coloneqq\left(\prod_{i=2}^{d}\sigma_{i}\right)^{1/(d-1)}$.
Clearly $\bm{c}^{\prime}+\mathcal{E}^{\prime\prime\prime}$ is now a body of
revolution about $\bm{e}_{1}$ whose volume is the same as that of
$\bm{c}^{\prime}+\mathcal{E}^{\prime\prime}$ (and hence also of
$\bm{c}+\mathcal{E}$). Note that
$\bm{c}^{\prime}+\alpha\mathcal{E}^{\prime\prime\prime}$ is also now a body of
revolution. Since $\sigma^{\prime}\geq\min_{2\leq i\leq d}\sigma_{i}$ we have
$B_{2}^{d}\cup\\{2\bm{e}_{1}\\}\subseteq\bm{c}^{\prime}+\mathcal{E}^{\prime\prime\prime}$,
and correspondingly since $\sigma^{\prime}\leq\max_{2\leq i\leq d}\sigma_{i}$
we have that
$\bm{c}^{\prime}+\alpha\cdot\mathcal{E}^{\prime\prime\prime}\subseteq\mathsf{conv}\left((\alpha_{t}\cdot
B_{2}^{d})\cup\\{2\bm{e}_{1}\\}\right)$.

Clearly
$\bm{c}^{\prime}+\mathcal{E}^{\prime\prime\prime},\bm{c}+\alpha\cdot\mathcal{E}^{\prime\prime\prime}$
now adhere to the reduced case of Definition 6.6. Since the update is monotone
as well (and still $\alpha\leq 1/d$) we can apply Claim 6.7. As
$\operatorname{\mathsf{vol}}(\mathcal{E}^{\prime\prime\prime})=\operatorname{\mathsf{vol}}(\mathcal{E})$,
this means we have

$A_{t+1}-A_{t}\geq C_{\ref{eqn:lb_step_main}}\cdot(P_{t+1}-P_{t})$

as desired. ∎

###### Proof of Claim 6.5.

For the first property, this is exactly the well-known fact that the best
ellipsoidal rounding for the simplex $\Delta_{d}$ (see e.g. [How97, Remark
1.1]) has approximation factor $d$.

Now we show the second property. Again because the ball rounds the simplex
$\Delta_{d}$ with approximation factor $d$, we have

$\frac{1}{d}\cdot\Delta_{d}\subseteq B_{2}^{d}\subseteq\Delta_{d}$

As a result of this, we have

$\displaystyle\log\left(\frac{\operatorname{\mathsf{vol}}(\bm{c}+\alpha\cdot\mathcal{E})}{\operatorname{\mathsf{vol}}(B_{2}^{d})}\right)$
$\displaystyle\leq\log\left(\frac{\operatorname{\mathsf{vol}}(\Delta)}{\operatorname{\mathsf{vol}}(B_{2}^{d})}\right)$
$\displaystyle\leq\log\left(\frac{\operatorname{\mathsf{vol}}(d\cdot
B_{2}^{d})}{\operatorname{\mathsf{vol}}(B_{2}^{d})}\right)$ $\displaystyle\leq
O(d\log d)$

And so

$\displaystyle\log\left(\frac{\operatorname{\mathsf{vol}}(\mathcal{E})}{\operatorname{\mathsf{vol}}(B_{2}^{d})}\right)$
$\displaystyle=\log\left(\frac{\operatorname{\mathsf{vol}}(\bm{c}+\alpha\cdot\mathcal{E})}{\operatorname{\mathsf{vol}}(B_{2}^{d})}\right)+d\log\left(\frac{1}{\alpha}\right)$
$\displaystyle\leq O\left(d\log\left(\frac{1}{\alpha}\right)\right)$
$\displaystyle\text{as }\alpha\leq\frac{1}{d}$

To establish the second property, it remains to show $d\log(1/\alpha)\leq
O((1/\alpha)\log(d))$. Observe that $x\mapsto\frac{x}{\log x}$ is increasing
for $x\geq e$, so we have

$\frac{d}{\log d}\leq
O\left(\frac{\nicefrac{{1}}{{\alpha}}}{\log(\nicefrac{{1}}{{\alpha}})}\right)$

for all $d\geq 2$ as $d\leq\nicefrac{{1}}{{\alpha}}$. Rearranging gives the
desired inequality and thus the second property. ∎

###  6.2 Analysis of the reduced case

In this section, we establish a lower bound on $\frac{\Delta A}{\Delta P}$,
assuming we are in the ‘reduced case’ defined in Definition 6.6. Observe that
in this case all relevant convex bodies
$\mathcal{E},\alpha\mathcal{E},c\cdot\bm{e}_{1}+\mathcal{E}^{\prime},c\cdot\bm{e}_{1}+\alpha^{\prime}\mathcal{E}^{\prime},\mathsf{conv}\left(\alpha\mathcal{E}\cup\\{\bm{z}\\}\right)$
are all bodies of revolution about the $x_{1}$-axis, so to analyze the
quantities involved we may instead look at any two-dimensional slice.
Accordingly we talk about the ellipses
$\mathcal{E},\alpha\mathcal{E},c+\mathcal{E}^{\prime},c+\alpha^{\prime}\mathcal{E}^{\prime}$
in this two-dimensional slice, where again $\mathcal{E}=B_{2}^{2}$, and
$c+\mathcal{E}^{\prime}$ and $c+\alpha^{\prime}\mathcal{E}^{\prime}$ are
defined by

$\displaystyle
c+\mathcal{E}^{\prime}=\left\\{(x,y)\in\mathbb{R}^{d}\middle|\left(\frac{x-c}{a}\right)^{2}+\left(\frac{y}{b}\right)^{2}\leq
1\right\\}$ $\displaystyle
c+\alpha^{\prime}\mathcal{E}^{\prime}=\left\\{(x,y)\in\mathbb{R}^{d}\middle|\left(\frac{x-c}{a}\right)^{2}+\left(\frac{y}{b}\right)^{2}\leq\alpha^{\prime
2}\right\\}$

for $a,b>0,c\in\mathbb{R}$. We also use for convenience $A=\frac{1}{\alpha}$
and $A^{\prime}=\frac{1}{\alpha^{\prime}}$ so that $\Delta A=A^{\prime}-A$.
Also note in this reduced case we have by symmetry that

$\Delta
P=\log\left(\frac{\operatorname{\mathsf{vol}}(c\cdot\bm{e}_{1}+\alpha^{\prime}\mathcal{E}^{\prime})}{\operatorname{\mathsf{vol}}(B_{2}^{d})}\right)-\log\left(\frac{\operatorname{\mathsf{vol}}(B_{2}^{d})}{\operatorname{\mathsf{vol}}(B_{2}^{d})}\right)=\log(a\cdot
b^{d-1})$

Our lower bound in this reduced case is the following:

######  Claim 6.8.

There exists a fixed constant $C_{\ref{eq:lb_cpct}}>0$ such that

$\frac{\Delta A}{\Delta
P}\geq\min\left(C_{\ref{eq:lb_cpct}},\frac{1}{10}\frac{A}{d}\right)$

Clearly this claim yields Claim 6.7 as a corollary, as by assumption in Claim
6.7 we have $A\geq d$ and so we get $\frac{\Delta A}{\Delta P}\geq\Omega(1)$.

The inner ellipses in this lower bound, and some relevant points used in the
proof of this claim, are depicted in Figure 6.

Figure 6: The inner ellipses in the two-dimensional lower bound. $\mathcal{O}$
is the origin. The black solid circle is the previous inner ellipse
$\alpha\mathcal{E}$, and the blue solid circle is the next inner ellipse
$c+\alpha^{\prime}\mathcal{E}^{\prime}$. The vertical dotted blue line $x=c$
through the center $c$ marks the location of the next inner ellipse on the
$x$-axis. The new point is $\bm{z}=2\bm{e}_{1}$, and $\overline{\bm{z}Q}$ is
one of the lines through $\bm{z}$ tangent to $\alpha\mathcal{E}$, with $Q$ the
point of tangency. $Q^{\prime}$ is the intersection of $\alpha\mathcal{E}$
with the $y$-axis on the same side of the $x$-axis as $Q$. $P^{\prime}$ is the
intersection of the line $x=c$ with $c+\alpha^{\prime}\mathcal{E}^{\prime}$ on
the same side as $Q$, and $P$ is the intersection of this line with
$\overline{\bm{z}Q}$. We denote the angle $\angle P\bm{z}c$ with $\varphi$.
(6.8)IIa$a,b\leq 16$Ib$a>16$ or $b>16$New ellipse close to
previousIIIIaIIa-i$A>2$IIa-iiIIa-ii-A$b\leq 100$IIa-ii-B$b>100$$A\leq 2$$a\leq
16$IIbIIb-iTerm I smallerIIb-iiTerm II smaller$a>16$New ellipse far from
previous Figure 7: Tree of cases in the lower bound

###### Proof.

We establish this claim through a geometric argument that we break down by
cases (the logical tree of cases is visualized in Figure 7). First, as the new
outer ellipse $c+\mathcal{E}^{\prime}$ contains $\mathcal{E}=B_{2}^{d}$ we
readily have that $a,b\geq 1$.

As the rightmost point of the new outer ellipse must be to the right of
$\bm{z}$, we have

$c+a>2$ (6.5)

As the leftmost point of the new inner ellipse must be to the right of the
leftmost point of the previous inner ellipse, we have

$c\geq\alpha^{\prime}a-\alpha$ (6.6)

######  Claim 6.9.

We have $\alpha^{\prime}\cdot b\leq\alpha$, or equivalently $A^{\prime}\geq
b\cdot A$.

###### Proof.

The geometry of this fact is visualized in Figure 6. We overload notation so
that $c$ will also denote the point $(c,0)$, the center of the new inner
ellipse. We denote $\mathcal{O}$ as the origin. Let $\overline{\bm{z}Q}$ be
one of the lines through $\bm{z}$ and tangent to $\alpha\mathcal{E}$, with $Q$
the point of tangency (the choice of which line is arbitrary, in the figure we
choose the one whose intersection with $\alpha\mathcal{E}$ is above the
$x$-axis). We let $P$ be the intersection of the vertical line through $(c,0)$
with $\overline{\bm{z}Q}$, and $P^{\prime}$ be the intersection of this line
with the ellipse $c+\alpha^{\prime}\partial\mathcal{E}^{\prime}$ on the same
side of the $x$-axis as $Q$.

Observe that $\alpha^{\prime}b=\overline{cP^{\prime}}$ as the vertical semi-
axis of the ellipse $c+\alpha^{\prime}\mathcal{E}$, and
$\alpha=\overline{\mathcal{O}Q^{\prime}}$. Due to the fact that
$c+\alpha^{\prime}\mathcal{E}^{\prime}\subseteq\mathsf{conv}\left(\alpha\mathcal{E}\cup\\{\bm{z}\\}\right)$,
the projection of both sets onto the $y$-axis satisfies the same inclusion,
and this gives the desired inequality. ∎

Observe that as $c+\mathcal{E}^{\prime}$ must contain both the points $(-1,0)$
and $(0,2)$, we have

$a\geq\frac{3}{2}$ (6.7)

Observe that we can split $\Delta P$ into two terms:

$\Delta P=\underbrace{(d-1)\log b}_{\text{I}}+\underbrace{\log a}_{\text{II}}$

First we show that if term I is larger, then we have a constant lower bound on
$\frac{\Delta A}{\Delta P}$.

######  Claim 6.10.

If $(d-1)\log b\geq\log a$, then $\frac{\Delta A}{\Delta
P}\geq\frac{1}{2}\frac{A}{d}$.

###### Proof.

Under the assumption, we have $\Delta P\leq 2(d-1)\log b$. Combining this with
Claim 6.9, we have

$\displaystyle\frac{\Delta A}{\Delta P}$
$\displaystyle\geq\frac{A^{\prime}-A}{2(d-1)\log b}$
$\displaystyle\geq\frac{b\cdot A-A}{2(d-1)\log b}$
$\displaystyle=\frac{b-1}{2\log b}\frac{A}{d-1}$
$\displaystyle\geq\frac{1}{2}\frac{A}{d}$

where the last line uses that $\frac{x-1}{2\log(x)}>\frac{1}{2}$ when $x>1$. ∎

In light of Claim 6.10, we can then assume in the sequel Term II is larger,
meaning that

$\Delta P\leq 2\log a$ (6.8)

Case I (New ellipse is close to the previous one). Assume that

$c+\alpha^{\prime}\cdot a\leq\frac{11}{10}\alpha$ (6.9)

i.e. that the rightmost point of the new inner ellipse is to the left of
$\frac{11}{10}$.

######  Claim 6.11.

In Case I, we have $\Delta A\geq\frac{4}{11}A$.

###### Proof.

We prove this by cases. First, if we assume that
$\alpha^{\prime}\leq\frac{\alpha}{2}$, we get $A^{\prime}\geq 2A$ and $\Delta
A\geq A$.

In the second case, we have $\alpha^{\prime}>\frac{\alpha}{2}$. We first use
this to show $c>0$. By (6.6) and (6.5) we have
$\frac{c+\alpha}{\alpha^{\prime}}\geq a>2-c$, so
$c(1+\alpha^{\prime})>2\alpha^{\prime}-a>0$ and so $c>0$.

Using (6.9) and that $c>0$, we have $\alpha^{\prime}a\leq\frac{11}{10}\alpha$.
Thus $A^{\prime}\geq\frac{10}{11}aA$. By (6.7) we get
$A^{\prime}\geq\frac{15}{11}A$, and finally $\Delta A\geq\frac{4}{11}A$. ∎

######  Claim 6.12.

In Case I, we have $A^{\prime}\geq\frac{10}{21}a\cdot A$.

###### Proof.

From (6.6) we also get the weaker lower bound $c\geq-\alpha$. Combined with
(6.9), this gives $\alpha^{\prime}a\leq\frac{21}{10}\alpha$, which is
equivalent to the desired inequality. ∎

We divide Case I into two sub-cases.

Case Ia ($a,b\leq 16$). First, assume that $a,b\leq 16$. Then $\Delta
P=\log(a\cdot b^{d-1})\leq d\log(16)$, and by Claim 6.11 we get

$\frac{\Delta A}{\Delta
P}\geq\frac{4}{11\log(16)}\frac{A}{d}\geq\frac{1}{10}\frac{A}{d}$

Case Ib ($a>16$ or $b>16$). Now assume that either $a$ or $b$ is greater than
$16$.

Combining Claim 6.9 and Claim 6.12 together, we get $A^{\prime
2}\geq\frac{10}{21}abA^{2}$, or $A^{\prime}\geq\sqrt{\frac{10}{21}ab}\cdot A$.
We have $\Delta A=A^{\prime}-A\geq\left(\sqrt{\frac{10}{21}ab}-1\right)A$. As
$ab\geq 16$ we get $\sqrt{ab}\geq 2\sqrt{\frac{21}{10}}$, so $\Delta
A=\left(\sqrt{\frac{10}{21}ab}-1\right)A\geq\sqrt{\frac{5}{21}ab}\cdot A$.

Using the analytic inequality that $\log x\leq\sqrt{x}$ for all $x>0$, we get
$\Delta P=\log a+(d-1)\log b\leq\sqrt{a}+(d-1)\sqrt{b}\leq d\cdot\sqrt{ab}$.

Combining these inequalites for $\Delta A$ and $\Delta P$, we obtain

$\frac{\Delta A}{\Delta
P}\geq\sqrt{\frac{5}{21}}\frac{A}{d}\geq\frac{4}{10}\frac{A}{d}$

Case II (New ellipse is far from the previous one). Assume that

$c+\alpha^{\prime}\cdot a>\frac{11}{10}\alpha$ (6.10)

######  Claim 6.13.

We have

$\alpha^{\prime}b\leq(2-c)\cdot\frac{\frac{\alpha}{2}}{\sqrt{1-\left(\frac{\alpha}{2}\right)^{2}}}$
(6.11)

###### Proof.

Again, the proof of this claim is pictured in Figure 6, where we construct the
points in the same way as in the proof of Claim 6.9. Let $\angle P\bm{z}c$ be
denoted by $\varphi$. Note that the angle $\angle Pc\bm{z}$ is a right angle,
and so $\tan\varphi=\frac{\overline{cP}}{\overline{cv}}$. The line
$\overline{c\bm{z}}$ has length $2-c$, so we get
$\overline{cP}=(2-c)\tan\varphi$. The segment $\overline{cP^{\prime}}$, of
length $\alpha^{\prime}b$, is contained within the segment $\overline{cP}$,
and so $\alpha^{\prime}b\leq(2-c)\tan\varphi$.

Observe that the angle $\angle\mathcal{O}Q\bm{z}$ is also a right angle.
Further, clearly the length of $\overline{\mathcal{O}Q}$ is $\alpha$ and the
length of $\overline{0v}$ is $2$. Since we have that $\varphi$ is also the
angle $\angle Q\bm{z}\mathcal{O}$, we get $\sin\varphi=\frac{\alpha}{2}$. Now
using the standard trigonometric identity that
$\tan\varphi=\frac{\sin\varphi}{\sqrt{1-\sin^{2}\varphi}}$ for
$\varphi\in[-\pi/2,\pi/2]$, we get the desired inequality. ∎

We split Case II into several sub-cases, as for Case I.

Case IIa ($a\leq 16$). First, we look at the case where $a\leq 16$.

Case IIa-i ($A\geq 2$). Assume $A\geq 2$.

######  Claim 6.14.

When $A\geq 2$, we have $\Delta A\geq\frac{1}{2}$.

###### Proof.

Adding (6.6) and (6.10) together gives $c>\frac{1}{20}\alpha$. Using this in
(6.11) and rearranging using the definitions of $A$ and $A^{\prime}$ yields

$A^{\prime}\geq
bA\cdot\frac{1}{1-\frac{1}{40}\frac{1}{A}}\left(1-\frac{1}{A^{2}}\right)$

and therefore we get the inequality

$\Delta A\geq
bA\cdot\frac{1}{1-\frac{1}{40}\frac{1}{A}}\left(1-\frac{1}{A^{2}}\right)-1$

and using $b\geq 1$, we obtain

$\Delta A\geq
A\cdot\frac{1}{1-\frac{1}{40}\frac{1}{A}}\left(1-\frac{1}{A^{2}}\right)-1$

To prove the claim, it suffices to show the right hand side exceeds
$\frac{1}{2}$ when $A\geq 2$. Upon rearranging, this is equivalent to the
inequality $A-\frac{77}{80}\frac{1}{A}\geq\frac{3}{2}$ when $A\geq 2$. ∎

Combining the assumption that $a\leq 16$ with (6.8) and Claim 6.14 yields
$\frac{\Delta A}{\Delta P}\geq\frac{1}{4\log 16}\geq\frac{1}{20}$.

Case IIa-ii ($A\leq 2$). Next, we look at the other case where $A\leq 2$.

Case IIa-ii-A ($b\leq 100$). Now we look at the case where $b\leq 100$.

######  Claim 6.15.

If $a\leq 16,A\leq 2,b\leq 100$, then there is $C_{\ref{eq:lb_cpct}}>0$ such
that

$\frac{\Delta A}{\Delta P}\geq C_{\ref{eq:lb_cpct}}$ (6.12)

###### Proof.

We show this by a compactness argument. By (6.8) and the assumption that
$a\leq 16$ we have $\frac{\Delta A}{\Delta P}\geq\frac{\Delta A}{2\log 16}$.
Now, observe that next outer and inner ellipsoids $c+\mathcal{E}^{\prime}$ and
$c+\alpha^{\prime}\mathcal{E}^{\prime}$ are fully determined by the parameters
$a,b,c,A,A^{\prime}$. Further, we assume without loss of generality that
$A^{\prime}$ is a function of the other parameters. This is because when
$A^{\prime}$ is decreased as much as possible while preserving the
monotonicity of the update, $\Delta A=A^{\prime}-A$ only decreases. To show a
lower bound on $\Delta A$ it then suffices to only do so in this hardest case.

Note that we have $1\leq a\leq 16,1\leq b\leq 100,-1\leq c\leq 2$, and $1\leq
A\leq 2$; thus all the parameters defining the next inner and outer ellipsoids
are bounded. Observe that $\Delta A$ is a continuous function of these
parameters, and as a continuous function of a compact set it attains its
minimum. Finally, we argue that it is impossible for the minimum of $\Delta A$
to be zero, and so the minimum is some strictly positive constant
$\frac{C_{\ref{eq:lb_cpct}}}{2\log 16}$, which suffices to prove the claim.

The following argument only concerns the inner ellipsoids, and can be pictured
in Figure 6. If $c=0$, then as the leftmost point of
$c+\alpha^{\prime}\mathcal{E}^{\prime}$ must be to the right of the leftmost
point of $\alpha\mathcal{E}^{\prime}$, we have $\alpha\geq\alpha^{\prime}a$.
But by (6.7), we have $\alpha\geq\frac{3}{2}\alpha^{\prime}$, so
$\alpha^{\prime}<\alpha$ and $\Delta A>0$. If $c\neq 0$ then the vertical
semi-axis of $c+\alpha^{\prime}\mathcal{E}^{\prime}$ must have length strictly
less than $\alpha$, and so $\alpha>\alpha^{\prime}b$. As $b\geq 1$, this also
gives $\alpha>\alpha^{\prime}$ and again $\Delta A>0$. ∎

Case IIa-ii-B ($b>100$). Observe that the horizontal axis of the next inner
ellipsoid $c+\alpha^{\prime}\mathcal{E}^{\prime}$ must be contained within the
interval $[-\alpha,2]$, thus we have that $2+\alpha\geq
2b\alpha^{\prime}>200\alpha^{\prime}$. Using the definitions of $A,A^{\prime}$
this is equivalent to $2+\frac{1}{A}>\frac{200}{A^{\prime}}$, i.e.
$A^{\prime}>\frac{200}{1+\frac{1}{A}}$. As $A\geq 1$ we get $2+\frac{1}{A}\leq
3$, and so $A^{\prime}\geq\frac{200}{3}$.

As $A\leq 2$, we obtain $\Delta A=A^{\prime}-A\geq\frac{194}{3}$. Now by (6.8)
and that $a\leq 16$ we have

$\frac{\Delta A}{\Delta P}\geq\frac{\Delta A}{2\log 16}\geq\frac{194}{6\log
16}\geq 11$

Case IIb ($a>16$). Now, we examine the case where $a>16$. Scaling (6.6) by
$\frac{11}{10}$ and adding it to (6.10), we have
$\frac{21}{10}c-\frac{1}{10}\alpha^{\prime}a\geq 0$, i.e.
$c>\frac{1}{21}\alpha^{\prime}a$. Using this in (6.11), using $b\geq 1$, using
the definitions of $A$ and $A^{\prime}$ and rearranging, we obtain

$A^{\prime}\geq
A\cdot\frac{1}{1-\frac{1}{42}\cdot\frac{a}{A^{\prime}}}\cdot\sqrt{1-\left(\frac{\alpha}{2}\right)^{2}}$

Using the inequalities $\sqrt{1-\left(\frac{x}{2}\right)^{2}}\geq
1-\frac{x^{2}}{7}$ for $0\leq x\leq 1$ and $\frac{1}{1-x}\geq 1+x$ for $0\leq
x\leq 1$, we have

$A^{\prime}\geq
A\left(1-\frac{\alpha^{2}}{7}\right)\left(1+\frac{1}{42}\frac{a}{A^{\prime}}\right)$

and thus $A^{\prime 2}-A\cdot
A^{\prime}\left(1-\frac{\alpha^{2}}{7}\right)-\frac{1}{42}\left(1-\frac{\alpha^{2}}{7}\right)\geq
0$, which implies by the quadratic formula that

$\displaystyle A^{\prime}$
$\displaystyle\geq\frac{A\left(1-\frac{\alpha^{2}}{7}\right)+\sqrt{A^{2}\left(1-\frac{\alpha^{2}}{7}\right)+\frac{4}{42}aA\left(1-\frac{\alpha^{2}}{7}\right)}}{2}$
$\displaystyle=A\left(1-\frac{\alpha^{2}}{7}\right)\cdot\frac{1+\sqrt{1+\frac{2}{21}\frac{a}{A\left(1-\frac{\alpha^{2}}{7}\right)}}}{2}$
$\displaystyle=A\left(1-\frac{\alpha^{2}}{7}\right)\cdot\left(1+\frac{\sqrt{1+\frac{2}{21}\frac{a}{A\left(1-\frac{\alpha^{2}}{7}\right)}}-1}{2}\right)$

Using the inequality $\sqrt{1+x}-1\geq\frac{2}{5}\min(x,\sqrt{x})$ for all
$x\geq 0$, we get that

$A^{\prime}\geq
A\left(1-\frac{\alpha^{2}}{7}\right)\left(1+\frac{1}{5}\min\left(\smash[b]{\underbrace{\frac{2}{21}\frac{a}{A\left(1-\frac{\alpha^{2}}{7}\right)}}_{\text{I}},\underbrace{\sqrt{\frac{2}{21}\frac{a}{A\left(1-\frac{\alpha^{2}}{7}\right)}}}_{\text{II}}}\right)\right)$
(6.13)

To finish this case, we show the lower bound in the case where either term in
the $\min$ of (6.13) is the smaller term.

Case IIb-i (Term I in (6.13) is smaller). In this case, (6.13) is equivalent
to

$\displaystyle A^{\prime}$ $\displaystyle\geq
A\left(1-\frac{\alpha^{2}}{7}\right)+\frac{2}{105}a$

Using the definition of $A$, we have $A^{\prime}\geq
A-\frac{1}{7A}+\frac{2}{105}a$, and so $\Delta
A\geq-\frac{1}{7A}+\frac{2}{105}a$. As $A\geq 1$, we have $\Delta
A\geq\frac{2}{105}a-\frac{1}{7}$.

Now by (6.8), we get

$\frac{\Delta A}{\Delta P}\geq\frac{\frac{2}{105}a-\frac{1}{7}}{2\log a}$

Now, we complete this case by noticing the right hand side is at least
$\frac{1}{35}$ when $a>16$.

Case IIb-ii (Term II in (6.13) is smaller). In this case, (6.13) is equivalent
to

$A^{\prime}\geq
A\left(1-\frac{\alpha^{2}}{7}\right)+\sqrt{\frac{2}{525}aA\left(1-\frac{\alpha^{2}}{7}\right)}$
(6.14)

Using the definition of $A$ and that $A\geq 1$, we have
$A\left(1-\frac{\alpha^{2}}{7}\right)=A-\frac{1}{7A}\geq-\frac{1}{7}$. Using
this and the definition of $\Delta A$ in (6.14), we have

$\Delta
A\geq-\frac{1}{7}+\sqrt{\frac{2}{525}aA\left(1-\frac{\alpha^{2}}{7}\right)}$

Further, as $0\leq\alpha\leq 1$ we get
$A\left(1-\frac{\alpha^{2}}{7}\right)=\frac{1}{\alpha}-\frac{\alpha}{7}\geq\frac{6}{7}$,
so

$\Delta A\geq-\frac{1}{7}+\sqrt{\frac{12}{3675}a}$

Now by (6.8), we get

$\frac{\Delta A}{\Delta
P}\geq\frac{-\frac{1}{7}+\sqrt{\frac{12}{3675}a}}{2\log a}$

We finish with the fact that the right hand side is at least $\frac{1}{65}$
when $a>16$. ∎

##  7 Details of Analysis in Section 4.2

Here, we give the details for the outstanding claims in Section 4.2, where we
also use the notation from that section (specifically, the definition of
parameters in (4.1)). We first give some well-known bounds on $e^{x}$.

######  Claim 7.1.

Well-known inequalities on $e^{x}$.

  1. 1.

$1+x\leq e^{x}$ for all $x\in\mathbb{R}$

  2. 2.

$1+x+\frac{x^{2}}{2}\leq e^{x}$ for $x\geq 0$

We will also use a more specialized upper bound on $e^{x}$.

######  Claim 7.2.

For $0\leq x\leq\frac{4}{3}$, we have $e^{x}\leq
1+x+\frac{x^{2}}{2}+\frac{x^{3}}{4}$.

###### Proof.

Using the Taylor series for $e^{x}$ about $0$, we get that

$\left(1+x+\frac{x^{2}}{2}+\frac{x^{3}}{4}\right)-e^{x}=\frac{x^{3}}{12}-\sum_{k=4}^{\infty}\frac{x^{k}}{k!}=x^{3}\left(\frac{1}{12}-\sum_{k=4}^{\infty}\frac{x^{k-3}}{k!}\right)$

Clearly $x^{3}\geq 0$ for $x\geq 0$, so it remains to show
$\frac{1}{12}-\sum_{k=4}^{\infty}\frac{x^{k-3}}{k!}\geq 0$ for $0\leq
x\leq\frac{4}{3}$. $\sum_{k=4}^{\infty}\frac{x^{k-3}}{k!}$ is increasing (the
derivative is clearly positive when $x\geq 0$), and we finish by noting:

$\frac{1}{12}-\left.\sum_{k=4}^{\infty}\frac{x^{k-3}}{k!}\right|_{x=\frac{4}{3}}=\left.\frac{1+x+\frac{x^{2}}{2}+\frac{x^{3}}{4}-e^{x}}{x^{3}}\right|_{x=\frac{4}{3}}>0$

∎

Now we show some facts used in Claim 7.5, which Claim 4.3 reduces to. The
proof of Claim 7.5 will reduce to the following analytic inequality.

######  Claim 7.3.

For all $\gamma\geq 0$,

$\frac{(e^{\gamma}-1)^{2}}{e^{2\gamma}-(1+\frac{\gamma}{4})^{2}}\leq\frac{3}{2}\gamma$

###### Proof.

For the numerator of the left hand side, we have
$(e^{\gamma}-1)^{2}=e^{2\gamma}-2e^{\gamma}+1\leq e^{2\gamma}-2\gamma-1$ using
Claim 7.1-(1), $1+x\leq e^{x}$. Further, $e^{\gamma}\geq 1+\frac{\gamma}{4}$
implies $e^{2\gamma}-(1+\frac{\gamma}{4})^{2}\geq 0$, so after multiplying
both sides by $e^{2\gamma}-(1+\frac{\gamma}{4})^{2}$ and rearranging it
suffices to show

$\frac{3}{2}\gamma\left(1+\frac{\gamma}{4}\right)^{2}-1-2\gamma\leq\left(\frac{3}{2}\gamma-1\right)e^{2\gamma}$

We split this into two cases, based on the value of $\gamma$. If
$\gamma\geq\frac{2}{3}$, then the right hand side is at least
$\left(\frac{3}{2}\gamma-1\right)(1+2\gamma+2\gamma^{2})$ using Claim 7.1-(2),
$1+x+\frac{x^{2}}{2}\leq e^{x}$, so it is sufficient to show
$\left(\frac{3}{2}\gamma-1\right)(1+2\gamma+2\gamma^{2})\geq\frac{3}{2}\gamma\left(1+\frac{\gamma}{4}\right)^{2}-1-2\gamma$.
Expanding both sides, this is equivalent to showing
$\frac{\gamma^{2}}{4}+\frac{93}{32}\gamma^{3}\geq 0$, which is clearly true
for $\gamma\geq 0$.

If $\gamma<\frac{2}{3}$, then we use Claim 7.2 to lower bound the right hand
side with
$\left(\frac{3}{2}\gamma-1\right)(1+2\gamma+2\gamma^{2}+2\gamma^{3})$, so it
is sufficient to show
$\left(\frac{3}{2}\gamma-1\right)(1+2\gamma+2\gamma^{2}+2\gamma^{3})\geq\frac{3}{2}\gamma\left(1+\frac{\gamma}{4}\right)^{2}-1-2\gamma$.
Similar to before, after expanding both sides this is equivalent to showing
$\frac{\gamma^{2}}{4}+\frac{93}{32}\gamma^{3}+\frac{3}{2}\gamma^{4}\geq 0$,
which is true for $\gamma\geq 0$. ∎

We also show some relations between the parameters in the update step. Recall
that we assumed $\alpha\leq\frac{1}{2}$.

######  Claim 7.4.

We have

  1. 1.

$b\leq 1+\frac{\gamma}{4}$

  2. 2.

$b\leq a$

  3. 3.

$\frac{(a-1)^{2}}{a^{2}-b^{2}}\leq 1$

  4. 4.

$b^{2}\geq 1+\alpha-\alpha^{\prime}$

###### Proof.

We start by showing (1). As
$\frac{1}{\alpha^{\prime}}=\frac{1}{\alpha}+2\gamma$, we have
$\alpha=\alpha^{\prime}+2\gamma\alpha\alpha^{\prime}$. Thus
$b=1+\gamma\alpha\alpha^{\prime}\leq 1+\gamma\alpha^{2}\leq 1+\gamma/4$ as
$\alpha^{\prime}\leq\alpha\leq\frac{1}{2}$.

For (2), observe that $b\leq 1+\frac{\gamma}{4}\leq 1+\gamma\leq e^{\gamma}=a$
using Claim 7.1-(1), $1+x\leq e^{x}$, so $a\geq b$.

To show (3), we first argue it is sufficient to show $1+b^{2}\leq 2a$. As a
consequence $-2a+1\leq-b^{2}$, so $(a-1)^{2}\leq a^{2}-b^{2}$. Because $b\geq
1$ by Claim 4.2-(2), from (2) we can say that $a^{2}-b^{2}\geq 0$, so that
$\frac{(a-1)^{2}}{a^{2}-b^{2}}\leq 1$.

Now to show $1+b^{2}\leq 2a$, we write as a series in terms of $\gamma$. On
the left hand side using (1), we have $1+b^{2}\leq
1+\left(1+\frac{\gamma}{4}\right)^{2}=2+\frac{\gamma}{2}+\frac{\gamma^{2}}{4}$.
Further, by Claim 7.1-(2), $e^{x}\geq 1+x+\frac{x^{2}}{2}$, we have that
$2a\geq 2+2\gamma+\gamma^{2}$. Clearly
$2+\frac{\gamma}{2}+\frac{\gamma^{2}}{4}\leq 2+2\gamma+\gamma^{2}$ when
$\gamma\geq 0$, so we are finished.

For (4), we have by definition that
$b^{2}=1+\alpha-\alpha^{\prime}+\frac{(\alpha-\alpha^{\prime})^{2}}{4}$, so
$b^{2}\geq 1+\alpha-\alpha^{\prime}$. ∎

As the proof of Claim 4.3 shows, that claim reduces to the following
inequality.

######  Claim 7.5.

$c^{2}\leq\frac{b^{2}-1}{b^{2}}\cdot(a^{2}-b^{2})$ (7.1)

###### Proof.

We first upper bound $c$ to reduce the number of variables in (7.1). As
$b=1+\frac{\alpha-\alpha^{\prime}}{2}$, we have
$2(b-1)=\alpha-\alpha^{\prime}$ and so $\alpha=\alpha^{\prime}+2(b-1)$. Thus

$c=-\alpha+\alpha^{\prime}\cdot
a=-(\alpha^{\prime}+2(b-1))+\alpha^{\prime}\cdot
a=\alpha^{\prime}\cdot(a-1)+2(1-b)a$

As $b\geq 1$ by Claim 4.2-(2), we have that $2(1-b)\leq 0$ and therefore

$c\leq\alpha^{\prime}\cdot(a-1)$

Using this in (7.1), it suffices to show $\alpha^{\prime
2}(a-1)^{2}\leq\frac{b^{2}-1}{b^{2}}\cdot(a^{2}-b^{2})$, which rearranges to

$\frac{b^{2}-1}{\alpha^{\prime 2}}\geq\frac{(a-1)^{2}b^{2}}{a^{2}-b^{2}}$

Using Claim 7.4-(4), this reduces to

$\frac{\alpha-\alpha^{\prime}}{\alpha^{\prime
2}}\geq\frac{(a-1)^{2}b^{2}}{a^{2}-b^{2}}$ (7.2)

The left hand side of (7.2) equals
$\frac{1}{\alpha^{\prime}}\left(\frac{\alpha}{\alpha^{\prime}}-1\right)$.
Because $\frac{1}{\alpha^{\prime}}=\frac{1}{\alpha}+2\gamma$, we have
$\frac{\alpha}{\alpha^{\prime}}-1=2\gamma\alpha$, so
$\frac{1}{\alpha^{\prime}}\left(\frac{\alpha}{\alpha^{\prime}}-1\right)=2\gamma\cdot\frac{\alpha}{\alpha^{\prime}}=2\gamma\cdot(1+2\gamma\alpha)$.
So it is sufficient to show

$2\gamma(1+2\gamma\alpha)\geq\frac{(a-1)^{2}b^{2}}{a^{2}-b^{2}}$ (7.3)

Now we will eliminate the other variables in this inequality to transform it
into a statement involving only $\gamma$. We have

$\displaystyle\frac{(a-1)^{2}b^{2}}{a^{2}-b^{2}}$
$\displaystyle=\frac{(a-1)^{2}}{a^{2}-b^{2}}\left(1+2\alpha\alpha^{\prime}\gamma+\alpha^{\prime
2}\alpha^{2}\gamma^{2}\right)$
$\displaystyle\leq\frac{(a-1)^{2}}{a^{2}-b^{2}}+\frac{\gamma}{2}+\alpha\frac{\gamma^{2}}{8}$

where the first line uses that $b=1+\alpha\alpha^{\prime}\gamma$, and the
second line inequality follows from Claim 7.4-(3) and the fact that
$\alpha^{\prime}\leq\alpha\leq\frac{1}{2}$. Thus we can reduce (7.3) to
$\frac{(a-1)^{2}}{a^{2}-b^{2}}\leq\frac{3}{2}\gamma+\frac{31}{8}\alpha\gamma^{2}$,
or further to

$\frac{(a-1)^{2}}{a^{2}-b^{2}}\leq\frac{3}{2}\gamma$ (7.4)

Using Claim 7.4-(1) and that $a=e^{\gamma}$, we have
$\frac{(a-1)^{2}}{a^{2}-b^{2}}\leq\frac{(e^{\gamma}-1)^{2}}{e^{2\gamma}-(1+\frac{\gamma}{4})^{2}}$,
so finally (7.4) reduces to

$\frac{(e^{\gamma}-1)^{2}}{e^{2\gamma}-(1+\frac{\gamma}{4})^{2}}\leq\frac{3}{2}\gamma$

which is proved in Claim 7.3. ∎

Recall in the proof of Claim 4.4 we defined
$\ell_{1}=\frac{1}{c+a},\ell_{2}=\sqrt{\frac{1}{\alpha^{2}}-\frac{1}{(c+a)^{2}}},r=\frac{a^{2}\ell_{1}^{2}}{b^{2}\ell_{2}^{2}}$.
That claim reduces to the following.

######  Claim 7.6.

$a-\alpha^{\prime}\cdot a\sqrt{\frac{1+r}{r}}\geq 0$

###### Proof.

As by definition $a\geq 0$, it suffices to show

$\alpha^{\prime 2}\cdot\left(\frac{1}{r}+1\right)\leq 1$ (7.5)

Observe that $\ell_{2}^{2}=\frac{1}{\alpha^{2}}-\ell_{1}^{2}$, so we can write
$\frac{1}{r}=\frac{b^{2}}{a^{2}}\left(\frac{1}{\alpha^{2}\ell_{1}^{2}}-1\right)$,
and hence rewrite (7.5) as

$\alpha^{\prime
2}\left(1+\frac{b^{2}}{a^{2}}\left(\left(\frac{c+a}{\alpha}\right)^{2}-1\right)\right)\leq
1$

Multiplying both sides by $\frac{\alpha^{2}}{\alpha^{\prime 2}}$ and
rearranging, this is equivalent to

$\frac{b^{2}}{a^{2}}\left((c+a)^{2}-\alpha^{2}\right)\leq\frac{\alpha^{2}}{\alpha^{\prime
2}}-\alpha^{2}$ (7.6)

Now, by definition of $c$ we can write $c+a=a(1+\alpha^{\prime})-\alpha$, so
that $(c+a)^{2}-\alpha^{2}=a^{2}(1+\alpha^{\prime})^{2}-2\alpha
a(1+\alpha^{\prime})$. Thus, (7.6) is equivalent to

$\frac{b^{2}}{a^{2}}(a^{2}(1+\alpha^{\prime})^{2}-2\alpha
a(1+\alpha^{\prime}))\leq\frac{\alpha^{2}}{\alpha^{\prime
2}}(1+\alpha^{\prime})(1-\alpha^{\prime})$

Dividing by $1+\alpha^{\prime}$ and simplifying the left hand side, this is
equivalent to

$b^{2}\left(1+\alpha^{\prime}-\frac{2\alpha}{a}\right)\leq\frac{\alpha^{2}}{\alpha^{\prime
2}}(1-\alpha^{\prime})$

which we show in Claim 7.7. ∎

######  Claim 7.7.

$b^{2}\left(1+\alpha^{\prime}-\frac{2\alpha}{a}\right)\leq\frac{\alpha^{2}}{\alpha^{\prime
2}}(1-\alpha^{\prime})$

###### Proof.

Using Claim 7.1-(1), $e^{-x}\geq 1-x$; and the fact that by definition
$\frac{1}{a}=e^{-\gamma}$, it suffices to show

$b^{2}\left(1+\alpha^{\prime}-2\alpha(1-\gamma)\right)\leq\frac{\alpha^{2}}{\alpha^{\prime
2}}(1-\alpha^{\prime})$

Using Claim 7.4-(4), this reduces further to

$(1+\alpha-\alpha^{\prime})(1+\alpha^{\prime}-2\alpha(1-\gamma))\leq\frac{\alpha^{2}}{\alpha^{\prime
2}}(1-\alpha^{\prime})$ (7.7)

We expand both sides of this inequality into polynomials involving $\gamma$
and $\alpha$, and then analyze the resulting expression. Using the definition
of $\alpha^{\prime}$, we have
$\alpha^{\prime}=\frac{\alpha}{1+2\gamma\alpha}$, and thus
$1+\alpha^{\prime}=\frac{1+2\gamma\alpha+\alpha}{1+2\gamma\alpha}$ and
$1-\alpha^{\prime}=\frac{1+2\gamma\alpha-\alpha}{1+2\gamma\alpha}$. We also
have $\frac{\alpha}{\alpha^{\prime}}=1+2\gamma\alpha$, and finally
$\alpha-\alpha^{\prime}=\frac{2\gamma\alpha^{2}}{1+2\gamma\alpha}$.
Substituting these equalities into (7.7), we obtain the equivalent inequality

$\left(\frac{1+2\gamma\alpha+\gamma\alpha^{2}}{1+2\gamma\alpha}\right)\left(\frac{1+2\gamma\alpha+\alpha}{1+2\gamma\alpha}-2\alpha(1-\gamma)\right)\leq(1+2\gamma\alpha)^{2}\left(\frac{1+2\gamma\alpha-\alpha}{1+2\gamma\alpha}\right)$

Multiplying both sides by $(1+2\gamma\alpha)^{2}$ and rearranging the terms so
that they are all on the same side, we get

$(1+2\gamma\alpha)^{3}(1+2\gamma\alpha-\alpha)-\left(1+2\gamma\alpha+\gamma\alpha^{2}\right)(1+2\gamma\alpha+\alpha-2\alpha(1-\gamma)(1+2\gamma\alpha))\geq
0$

Next, we expand this inequality:

$\displaystyle
16\alpha^{4}\gamma^{4}-16\alpha^{4}\gamma^{3}+8\alpha^{4}\gamma^{2}+24\alpha^{3}\gamma^{3}-12\alpha^{3}\gamma^{2}+12\alpha^{2}\gamma^{2}+2\alpha^{3}\gamma-2\alpha^{2}\gamma+2\alpha\gamma\geq
0$

As $\gamma\alpha\geq 0$, we can divide both sides of this inequality by
$2\gamma\alpha$. Grouping by powers of $\alpha$, we obtain:

$4\alpha^{3}\gamma\left(2\gamma^{2}-2\gamma+1\right)+\alpha^{2}\left(12\gamma^{2}-6\gamma+1\right)+\alpha(6\gamma-1)+1\geq
0$

Upon inspection, both quadratics $2\gamma^{2}-2\gamma+1$ and
$12\gamma^{2}-6\gamma+1$ are positive for all $\gamma$. Thus we only need to
show $\alpha(6\gamma-1)+1\geq 0$, but this is clear from writing it as
$1-\alpha+6\gamma\alpha\geq 0$ and using that $\alpha\leq 1$.

∎

## References

  * [AHV05] Pankaj K Agarwal, Sariel Har-Peled and Kasturi R Varadarajan  “Geometric approximation via coresets”  In _Combinatorial and computational geometry_ 52.1, 2005, pp. 1–30
  * [AS10] Pankaj K Agarwal and R Sharathkumar  “Streaming algorithms for extent problems in high dimensions”  In _Proceedings of the Symposium on Discrete Algorithms_ , 2010, pp. 1481–1489
  * [AGM15] Shiri Artstein-Avidan, Apostolos Giannopoulos and Vitali D Milman  “Asymptotic Geometric Analysis, Part I”  American Mathematical Soc., 2015
  * [BMV23] Aditya Bhaskara, Sepideh Mahabadi and Ali Vakilian  “Tight Bounds for Volumetric Spanners and Applications”, 2023  arXiv:2310.00175 [cs.DS]
  * [BBKLY18] Avrim Blum et al.  “Approximate Convex Hull of Data Streams”  In _Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP)_ 107, 2018, pp. 21:1–21:13
  * [BLM06] J Bourgain, J Lindenstrauss and V Milman  “Estimates related to Steiner symmetrizations”  In _Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 1987–88_ , 2006, pp. 264–273  Springer
  * [Cla10] Kenneth L. Clarkson  “Coresets, Sparse Greedy Approximation, and the Frank-Wolfe Algorithm”  In _ACM Trans. Algorithms_ 6.4, 2010
  * [GK10] Eugene Gover and Nishan Krikorian  “Determinants and the volumes of parallelotopes and zonotopes”  In _Linear Algebra and its Applications_ 433.1, 2010, pp. 28–40
  * [How97] Ralph Howard  “The John ellipsoid theorem”  In _University of South Carolina_ , 1997
  * [JLLV21] He Jia, Aditi Laddha, Yin Tat Lee and Santosh Vempala  “Reducing Isotropy and Volume to KLS: An $O^{*}(n^{3}\psi^{2})$ Volume Algorithm”  In _Proceedings of the Symposium on Theory of Computing_ , 2021, pp. 961–974
  * [Joh48] Fritz John  “Extremum problems with inequalities as subsidiary conditions”  In _Studies and Essays Presented to R. Courant on his 60th Birthday_ Interscience Publishers, Inc, 1948, pp. 187–204
  * [KY05] P. Kumar and E.. Yildirim  “Minimum-Volume Enclosing Ellipsoids and Core Sets”  In _J. Optim. Theory Appl._ 126.1 USA: Plenum Press, 2005, pp. 1–21
  * [MMO22] Yury Makarychev, Naren Sarayu Manoj and Max Ovsiankin  “Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes”  In _Proceedings of the Conference on Learning Theory_ , 2022
  * [MGSS] Asish Mukhopadhyay, Eugene Greene, Animesh Sarker and Tom Switzer  “Approximate minimum spanning ellipse in the streaming model”
  * [MSS10] Asish Mukhopadhyay, Animesh Sarker and Tom Switzer  “Approximate ellipsoid in the streaming model”  In _International Conference on Combinatorial Optimization and Applications_ , 2010, pp. 401–413
  * [Nes08] Yurii Nesterov  “Rounding of convex sets and efficient gradient methods for linear programming problems”  In _Optimisation Methods and Software_ 23.1 Taylor & Francis, 2008, pp. 109–128
  * [RB97] Elon Rimon and Stephen P. Boyd  “Obstacle Collision Detection Using Best Ellipsoid Fit”  In _J. Intell. Robotics Syst._ 18.2 USA: Kluwer Academic Publishers, 1997, pp. 105–126
  * [Sta08] Peter Stange  “On the efficient update of the Singular Value Decomposition”  In _PAMM_ 8.1, 2008, pp. 10827–10828
  * [Tod16] Michael J. Todd  “Minimum-Volume Ellipsoids: Theory and Algorithms”  Philadelphia, PA, USA: SIAM-Society for IndustrialApplied Mathematics, 2016
  * [TY07] Michael J. Todd and E. Yildirim  “On Khachiyan’s Algorithm for the Computation of Minimum-Volume Enclosing Ellipsoids”  In _Discrete Appl. Math._ 155.13, 2007, pp. 1731–1744
  * [WY22] David P Woodruff and Taisuke Yasuda  “High-dimensional geometric streaming in polynomial space”  In _Proceedings of the Symposium on Foundations of Computer Science_ , 2022, pp. 732–743