# iTUAVs: Intermittently Tethered UAVs for Future Wireless Networks

Nesrine Cherif1, Wael Jaafar1, Evgenii Vinogradov1, Halim Yanikomeroglu, Sofie
Pollin and Abbas Yongacoglu

###### Abstract

We propose the intermittently tethered unmanned aerial vehicle (iTUAV) as a
tradeoff between the power availability of a tethered UAV (TUAV) and
flexibility of an untethered UAV. An iTUAV can provide cellular connectivity
while being temporarily tethered to the most adequate ground anchor. Also, it
can flexibly detach from one anchor, travel, then attach to another one to
maintain/improve the coverage quality for mobile users. Hence, we discuss here
the existing UAV-based cellular networking technologies, followed by a
detailed description of the iTUAV system, its components, and mode of
operation. Subsequently, we present a comparative study of the existing and
proposed systems highlighting the differences of key features such as mobility
and energy. To emphasize the potential of iTUAV systems, we conduct a case
study, evaluate the iTUAV performance, and compare it to benchmarks. Obtained
results show that with only 10 anchors in the area, the iTUAV system can serve
up to 90% of the users covered by the untethered UAV swapping system.
Moreover, results for a small case study prove that the iTUAV allows to
balance performance/cost and can be implemented realistically. For instance,
when user locations are clustered, with only 2 active iTUAVs and 4 anchors,
achieved performance is superior to that of the system with 3 TUAVs, while
when considering a single UAV on a 100 minutes event, a system with only 6
anchors outperforms the untethered UAV as it combines location flexibility
with increased mission time.

##  I Introduction

††N. Cherif and A. Yongacoglu are with uOttawa, Canada. W. Jaafar is with
École de Technologie Supérieure, Canada, E. Vinagradov and S. Pollin are with
KU Leuven, Belgium. H. Yanikomeorglu is with Carleton University, Canada. This
work is funded by Huawei Canada, Natural Science and Engineering Research
Council of Canada (NSERC), and Research Foundation Flanders (FWO), projects
no. S003817N (OmniDrone) and G098020N. ∗Authors have contributed equally.

What are the advantages of UAV-mounted wireless communications? It increases
the chances of a stable Line-of-Sight (LoS) dominated channel to ground
terminals [1]. UAVs can also move and optimize their locations to satisfy the
dynamic service demand [2, 3]. These two features represent the core of all
innovative wireless communication solutions enabled by Unmanned Aerial
Vehicles (UAVs), including UAV base stations (UAV-BSs), also called on-board
radio nodes (UxNB) by the 3rd Generation Partnership Project (3GPP). The
limited battery capacity is the main challenge to fully unleash the UAV-BS
potential. To overcome this issue, several solutions have been proposed such
as i) deploying recharging stations, ii) battery or UAV swapping, and iii)
laser charging. Moreover, providing UAVs with permanent energy supply through
a tether, a.k.a., tethered UAV (TUAVs), has been proposed as an alternative to
the aforementioned solutions. Nevertheless, this concept offers unlimited
flight time at the expense of limited mobility due to its predetermined
hovering region [4].

Consequently, we propose here a novel development to the operation mode of the
TUAV system, which would make it more flexible and thus more attractive to
industry. It consists on the introduction of an agile tether that can be
attached/detached to/from existing infrastructures, called ground anchors,
such as UAV and electric vehicle charging stations, illustrated in Fig. 1. We
call this novel system intermittently tethered UAV (iTUAV). It is noteworthy
that “ground anchor” and “anchor” are used interchangeably throughout the
paper.

Figure 1: Proposed iTUAV system.

##  II UAV-based Communications: A Review

In recent years, the use of UAVs to provide cellular connectivity has
attracted increasing attention and their potential to complement terrestrial
networks has been extensively investigated. Due to their agility and
flexibility, UAV-BSs temporary handle spikes in data demands during short-term
events, such as large concerts and games [5]. However, UAV-BS operations are
hampered by limited flying times, typically between 30 minutes and a few
hours. To tackle this problem, numerous solutions have been investigated,
e.g., battery recharging and swapping, UAV swapping, laser charging, and TUAV
systems.

###  II-A Battery Recharging and Swapping

To overcome the battery limitation, one can design a system where a UAV-BS
flies back to a dedicated charging station to either recharge its battery or
exchange it for a filled one [6].

_Critique:_ Since UAV-BSs spend time to travel and recharge at a dockstation
or land for battery swapping, these solutions cause frequent service
interruptions, which is not ideal for stringent connectivity services, such as
safety applications.

###  II-B UAV-BSs Swapping

In order to eliminate service interruptions, several works have proposed
continuous UAV-BS swapping. In [7] proposed automating UAV swapping for
continuous cellular connectivity by monitoring UAV-BSs battery levels.

_Critique:_ These approaches offer high UAV-BS deployment flexibility and
sustained cellular services. However, their advantages come at the expense of
higher capital and operational expenditures (CAPEX/OPEX), due to a larger UAV
fleet.

###  II-C Laser Charging

Another solution consists of recharging UAV-BSs on-the-fly through laser
beaming. This technology can be implemented with a laser array oriented
through a set of mirrors or diamonds aimed at the UAV-BS’s collecting lens. In
spite of its great potential, laser beaming requires large collecting lenses
and high laser power, two factors that limit its deployment, especially in
urban areas. Alternatively, distributed laser charging (DLC) involves the use
of photo-voltaic cells instead of a collecting lens, which is practical and
cost-effective for small UAV-BSs [8]. Unlike laser beaming, DLC uses less than
one kilowatt transmit power, thus favoring its deployment anywhere. Finally,
efficient DLC requires LoS between the charging source and UAV-BS.

_Critique:_ Due to health-related concerns, laser beaming with high power
cannot be used in densely populated areas. In the meanwhile, DLC may perform
poorly in non-LoS conditions. Moreover, due to its slow charging regime, DLC
is only efficient when the UAV-BS is on stand-by [8].

###  II-D TUAV Systems

TUAV does not suffer from short operation time. Its main idea involves linking
the UAV to the ground using a tether that provides both power supply and high-
capacity backhaul. Consequently, the limited TUAV mobility is compensated by a
longer operation time and higher backhauling capacity. [4] and [9] introduced
specific constraints to TUAVs such as limited tether length and safety
considerations to avoid tangling the tether around surrounding buildings.
Also, they assumed that the tether serves both as power cable and wired
backhaul link. This assumption implies complex and high cost tether and anchor
designs. Alternatively, a simpler design can support power supply only, while
relying on wireless backhauling through either radio or free-space optics
[10].

_Critique:_ The main disadvantage is the reduced flexibility due to highly
restricted flying distance. Moreover, backhauling through a tether implies
higher equipment cost. Thus, they may be considered a good alternative to
terrestrial BSs (TBSs) and by far do not offer the same advantages as UAV-BSs.

##  III Intermittently Tethered UAVs

Given the limited hovering areas of TUAVs and battery-limited operation of
untethered UAVs, we propose here a compromise solution, a.k.a. iTUAV, which
offers both the flexibility of a UAV and the sustainability of a TUAV. In what
follows, we present the iTUAV system components, operation mode, and a
qualitative features comparison to existing technologies.

###  III-A System Components

An iTUAV-aided communication system involves several components shown in Fig.
1 and described as follows:

#### iTUAV

An iTUAV is a small UAV equipped with a lightweight 5G New Radio (NR) UxNB for
communication, e.g., Ericsson’s network-on-a-drone. Specifically, the iTUAV
has the following modules:

  * •

Access: As specified in 3GPP TR 22.829, UxNB is able to connect to the 5G core
network and operate as a BS, via a wireless backhaul link, and can bootstrap
as a BS, from the core network’s perspective. To do so, we assume that the
UxNB is equipped with multiple antennas enabling directional patterns towards
users [11].

  * •

Backhaul: The backhaul can be provided by a wireless gateway (e.g., a nearby
TBS, TUAV, or satellite) or through an associated anchor, if it provides
backhauling services. In the case of a wireless backhaul, integrated access
and backhaul (IAB) can be leveraged [10, 11]. Since 3GPP does not enforce any
particular IAB implementation, radio access and backhauling can use different
frequency bands or the same spectrum. The latter is possible since a UxNB
supports directional antenna arrays to spatially separate the links.

  * •

Power: To reduce costs, we assume that the iTUAV is equipped with a small
battery that enables short flight times to reach anchors and reconnect through
a tether. Moreover, each iTUAV is equipped with a socket that allows it to
attach a retractable tether from the anchor and that can be used
simultaneously to power the motors in-flight and to recharge the battery. This
design suggests landing over the anchor to attach the iTUAV, thus causing
service delays. Alternatively, the iTUAV can be equipped with a lightweight
tether that is dropped vertically to the anchor rather than landing on it
[12].

#### Ground anchors

These are mainly power supply sources used to sustain iTUAV operations. A
ground anchor may include one or several of the following components. First,
it must have access to the power grid and be equipped with adequate power
converters to support different types and sizes of UAVs and electric vehicles.
Second, it may be provided with standardized sockets to plug UAVs and electric
vehicles. Third, it may include power tethers dedicated for iTUAVs with power
sockets. Fourth, it may have a battery swapping station, which may be used by
UAV-BSs. Additionally, the anchor can offer backhauling through a wired link
combined with on-site routing equipment. The versatility of the anchor role
favors its business and practical interests as part of the smart city
infrastructure. For instance, anchors can be easily and seamlessly integrated
to lampposts, road signs, and lights.

#### Gateway

This is the entry-point of the iTUAV to the core network. It can be the
routing equipment of an anchor, a TBS, a TUAV, or a satellite. Except for the
anchor that allows a direct wired connection to the core network, the other
alternatives require wireless links with the iTUAV. Although wireless
transmissions are less efficient than wired ones, communicating with a TBS
equipped with highly directional antenna arrays using IAB is an effective and
cheap alternative.

Figure 2: Operation steps of the iTUAV system (the solid black arrows show the
users’ motion direction; the gray dashed arrow represents the ground anchor
selection; the green solid line is the tether that connects the iTUAV to the
anchor; the green and orange beams are the access and backhaul links,
respectively.

###  III-B System Operation

We assume a communication system deployed in an urban environment, e.g., smart
city, consisting of iTUAVs, TBSs, ground anchors, and mobile ground users. The
main goal of an iTUAV-aided communication network is to meet the performance
requirements related to ubiquitous coverage, e.g., during temporary events,
and to on-demand network densification due, for instance, to peak traffic
demands. Fig. 2 details the operational steps of this system, explained below:

  1. 1.

A TBS detects users that cannot be reliably served. These users are clustered
then assigned to an iTUAV.

  2. 2.

To serve users’ clusters, the optimal location of the iTUAV and its associated
anchor are jointly determined. The formulation and solution of this problem
may take into account limitations, such as the propagation environment,
backhaul link quality and TBS resources.

  3. 3.

The iTUAV flies to the anchor and connects to it through a retractable power
tether. Then, it travels to its optimal location and hovers to serve the
associated cluster.

  4. 4.

Since users are mobile, the optimal location of the iTUAV (determined in the
previous steps) may become out of reach of the tether’s length. In this case,
the new optimal location and associated anchor must be recalculated.
Subsequently, the iTUAV detaches itself from the current anchor and re-
executes step 3.

###  III-C iTUAV Systems Versus Existing Technologies

The idea behind iTUAV emerges from the tradeoff between mobility and power
availability. In what follows, we compare the UAV-based cellular networks,
namely iTUAV, UAV (i.e., untethered UAV-BS), TUAV, and TBS:

  * •

Mobility: UAVs equipped with BSs gained popularity thanks to their exceptional
3D mobility. A typical UAV-BS use-case consists of providing connectivity for
temporary events with high traffic demands. Such scenarios cannot be handled
by terrestrial cellular networks due to the fixed nature of TBSs. In contrast,
TUAVs and iTUAVs are much less constrained, and thus can leverage their
partially limited mobility to better serve users. Nevertheless, a TUAV is
permanently fixed to an anchor, which limits its region of activity, compared
to an iTUAV, which is able to travel from one anchor to another. Consequently,
iTUAVs cover wider areas than TUAVs.

  * •

Re-deployment Flexibility: UAVs are valued for their rapid deployment feature,
due to their high flying speed. An iTUAV can be re-deployed almost as quickly,
either by relocating within a hovering region, subject to the tether length,
or by traveling to the closest anchor to the targeted location. Note that the
inherent re-location flexibility of a TUAV is strongly linked to the length of
the tether and thus to its hovering region. That means, if redeployment is
required in an area outside the hovering region, the TUAV cannot satisfy the
new requirement. Finally, TBSs lack this feature due to their fixed nature.

  * •

Cellular Reliability: A terrestrial network is considered reliable when its
TBSs deployment is optimized and does not experience substantial coverage
gaps. An aerial BS increases the probability of LoS to communicate with ground
users and thus is capable of providing a similar performance as a TBS.
However, untethered UAV-BSs rely on wireless backhauling, which is limited
compared to a TBS wired backhaul. A TUAV system offers better reliability due
to its wired backhaul; nevertheless, its limited motion prevents it from
offering a highly reliable coverage. Finally, an iTUAV ensures a better
cellular reliability than UAV/TUAV systems due to its flexibility in
connecting with different anchors to achieve better access/backhaul links.
With enough available anchors, iTUAVs can achieve similar performance to TBSs.

  * •

Backhaul Availability: A terrestrial network provides a highly available
backhaul through fiber links and point-to-point RF transmissions. Similarly,
TUAV-based solutions assume that backhauling is carried through fiber links
aggregated with the power supply within the tether. By contrast, iTUAVs are
expected to operate opportunistically with both wireless and wired
backhauling. Indeed, whenever the anchor provides a tether with a fiber optic
data link, backhauling goes through it. However, if an anchor is exclusively a
power source or when an iTUAV is traveling between anchors, then it has to
rely on wireless links to most adequate TBSs or to other wireless gateways.
Finally, untethered UAV-BSs rely solely on the wireless backhaul.

  * •

Energy Availability: Clearly, the untethered UAV-BS has the lowest power
capacity. By contrast, energy for TBSs and TUAVs is available continuously.
iTUAVs, although occasionally traveling, enjoy a very high energy
availability. When an iTUAV is attached to an anchor, it has unlimited access
to power as TUAVs. This energy is used for both iTUAV operation and battery
recharging. However, when it is traveling between anchors, it relies
exclusively on its on-board battery. Note that locations of anchors and
battery capacity must be carefully and jointly designed in order to avoid
draining the iTUAV’s battery when traveling between anchors.

  * •

Infrastructure Reuse: Terrestrial cellular infrastructure suffers from a low
usage rate due to users with sporadic traffic demands. In TUAV systems, the
anchor is permanently powering a single or several TUAVs through tether(s),
resulting in small or no opportunities to reuse the tether or the power supply
of the anchor. By contrast, an iTUAV is only attached to an anchor for the
time of its mission, then it releases the tether and flies to a different
location. The low usage rate of anchors by iTUAVs favors their reuse for other
applications such as recharging flying taxis, cargo UAVs, and electric
vehicles. Moreover, the fleet of iTUAVs is much smaller than the one
considered by UAV swapping. Infrastructure reuse substantially increases
iTUAVs’ economic viability. Moreover, the additional generated revenue from
anchors reuse can offset the investment of extensive anchor networks and the
expenses thereafter (e.g., rental of rooftops).

  * •

CAPEX: One of the main concerns in setting up cellular services is the amount
of initial investment needed. TBSs are usually costly. Locations for their
deployment need to be purchased or leased, and they require expensive
electrical and communications equipment. In contrast, UAVs are less expensive,
but have limitations that need to be considered. This typically leads to
purchasing a high number of UAVs, batteries, and recharging stations to enable
UAV swapping, battery recharging/swapping. In the case of TUAVs, the initial
investment consists of buying UAVs with their tether anchors for power supply
and communication. Due to the limited tether length, covering a large area
would require the deployment of several TUAVs, which may rapidly increase
costs. Like TUAVs, iTUAVs rely on anchors, but with lighter functionalities.
Indeed, Compared to TUAV systems, a smaller number of iTUAVs but a slightly
higher number of anchors can sustain wireless services in large areas.

  * •

OPEX: Terrestrial networks still face high operating costs for equipment
maintenance. The use of UAVs instead requires sophisticated software and
professional UAV pilots to lead missions and organize recharging/swapping
operations. For TUAV and iTUAV systems, in addition to operation software,
maintenance of UAVs and anchors is needed. However, the cost of maintaining a
UAV is expected to be higher than that for an anchor. Hence, OPEX might be
slightly lower for iTUAVs due to their forecast smaller number, but slightly
higher number of anchors. Finally, iTUAV anchors can generate additional
revenue through their reuse, which is expected to significantly offset the
CAPEX/OPEX costs.

Based on the foregoing discussion, iTUAV systems present great potential to
compete with or complement existing cellular technologies. They represent a
promising middle-solution between the mobility features of UAVs and the
operational sustainability of TUAVs and TBSs.

##  IV Case Study

To corroborate our findings on iTUAV systems, we investigate here their
achievable performance in terms of average number of covered users as a
function of terrestrial users density and of its sustainability. These results
are compared against those of UAV and TUAV systems.

###  IV-A Simulation setup

We consider a $3\times 3$ km2 urban area where a single UAV (or a TUAV or an
iTUAV) is deployed to provide cellular coverage for terrestrial users
equipment (UEs). The transmit power is set to $P_{t}=30$ dBm and the UE
receiver sensitivity is $P_{\min}=-70$ dBm [1], which translates to a path
loss threshold of $100$ dB. We assume that the air-to-ground channels follow
the probabilistic line-of-sight (LoS) and non-LoS (NLoS) propagation model
[13], operating at frequency $f_{c}=2$ GHz. The average height of anchors is
$50$ m and the maximal tether length for both the TUAV and iTUAV is set to
$150$ m [9]. For the sake of simplicity, we assume that the TUAV (resp. iTUAV)
minimum inclination angle that prevents tangling around surrounding buildings
and ensures the safety of the tether is set to 0∘. The UEs are distributed
according to the Thomas point process. With this distribution, clustering of
UEs is modeled through the coefficient of variation (CoV) of the Voronoi cell
area around each user [14]. For instance, when $\text{CoV}=1$, the UEs are
uniformly distributed according to the Poisson point process, whereas a higher
CoV represents more clustered users around a virtual cluster head. At each
realization, i.e., UEs and anchors geographical distributions, the iTUAV
determines the optimal anchor and attaches to it to provide cellular coverage
to the highest number of UEs. In contrast, the untethered UAV freely
determines and reaches the optimal 3D location that maximizes its coverage
[1], whereas the TUAV, constrained to its pseudo-static deployment, relocates
withing its hovering region to cover the maximal number of UEs [9]. Finally,
results are averaged over both the UEs’ geographical distribution and anchor
positions in each iteration.

Given the identified constraints of iTUAV (resp. UAV and TUAV) system, the
formulated problems aim to maximize the cellular coverage of iTUAVs (resp.
UAVs and TUAVs) through the optimization of the UAV-BS 3D location and ground
anchor association (iTUAV). Although seeming different, these problems are
convex [1, 15]. Hence, they can be solved using MOSEK parser in the CVX
package of Matlab.

###  IV-B Results and Discussion

Figure 3: Coverage performance of UAV (with swapping), TUAV, and iTUAV
systems, for different user distributions.

Figure 4: Coverage performance of UAV, TUAV, and iTUAV systems for a temporary
event of 100 minutes ($\text{CoV}=3$).

Figure 5: Coverage performance of TUAV and iTUAV systems (different setups).

Fig. 5 shows the average number of users covered by the single serving UAV as
a function of the CoV for different UAV systems, namely, UAV, TUAV, and iTUAV.
Although TUAV and iTUAV deploy a single UAV, the UAV system assumes UAV
swapping in order to ensure a similar service continuity over time [7]. As
expected, the UAV presents the best coverage performance thanks to its optimal
placement. By contrast, the TUAV is extremely limited in its flying range by
the tether/anchor location, thus often missing the best placement achieved by
the UAV. Alternatively, the iTUAV outperforms the TUAV due to the availability
of several anchors, which allows it to select the best one and optimally place
itself to cover a higher number of users. Nevertheless, the iTUAV system
performs below the UAV, since it may miss the optimal placement if none of the
anchors is located close enough (subject to the tether’s length) to the UAV
optimal location. With more anchors, the iTUAV exploits near-optimal hovering
locations, and thus achieves better coverage performance. Finally, as the CoV
increases, coverage improves for all systems. Since UEs are more clustered,
UAV communicates through better channels to a higher number of them.

Fig. 5 compares the performances of the UAV without swapping (w/o swap), UAV
with swapping (w/ swap), TUAV, and iTUAV systems in terms of the average
number of covered users per time unit (min.). Specifically, we define a
cellular radio access mission consisting of deploying one UAV within a target
area to provide cellular connectivity during a temporary event of 100
minutes.111This assumption implies no UAV swapping for the untethered UAV and
the mission of the UAV is hence limited by the battery lifetime. During this
event, we aim to maximize the average number of connected users to the mobile
UAV. The average is calculated over multiple network topologies (i.e.,
different scenarios for users’ and anchors’ locations) and time. We assume
different battery capacities for the UAV (w/o swap), ranging between 30 and 60
minutes of flying time, while the iTUAV relies on a number of anchors, between
3 and 10. We notice that the UAV (w/o swap) coverage performance is low with a
small battery capacity (e.g., 8 users per min. with a battery of 30 min.), but
it improves with a larger battery capacity (e.g., 16.8 users per min. with a
battery of 60 min.). However, the TUAV can continuously serve 8 users per
minute. The TUAV performance is mainly limited by the tether that prevents the
UAV from hovering at a better location where it could serve more users. With
more anchors, the iTUAV enjoys better performance over time as it can also
serve more users owing to its mobility and stable power source, i.e., through
the tether and the on-board battery when traveling between anchors. Finally,
considering UAV (w/ swap), this system is equivalent to having an unlimited
battery capacity while enjoying full motion flexibility, thus it achieves the
best performance, i.e., around 26 users in average are covered through time.
This performance, however, comes at the expense of an additional investment in
a higher number of UAVs and more complex operations. In a nutshell, we
conclude that, thanks to its unlimited power and flexible association to
anchors, the iTUAV is able to sustain a reliable cellular service over time,
which is better than the UAV (w/o swap) and TUAV systems, but slightly below
that of the UAV (w/ swap) reference system. If a higher number and more
adequate locations of anchors are available, iTUAV performance is expected to
reach that of the UAV (w/ swap).

In Fig. 5, we illustrate the cellular coverage performance of iTUAV and TUAV
systems with multiple UAVs as function of the CoV. When the users are very
clustered, the iTUAV system performance mainly depends on the number of
anchors, and a system with only 1 active iTUAV but 3 anchor locations even
outperforms a system with 2 fixed TUAVs. A system with only 2 iTUAVs and 4
anchor locations, clearly achieves the best performance in clustered users
scenarios. This is due to the opportunistic iTUAV behavior to move freely
between anchors and associate with the best one. In contrast, the TUAV system
has less leverage on relocating due to its static deployment.

##  V Challenges and Future Directions

As research of TUAV/iTUAV systems is in its infancy, several challenges
remain. Next, we discuss some key issues:

  * •

New anchor, UAV, and tether designs: Current TUAVs are built with the tether
already attached at both anchor and UAV ends, such that attaching/detaching
the tether must be executed manually. To achieve more flexibility to iTUAVs,
two options can be considered: 1) the tether is within the anchor and it
provides an easy-clip attach/detach system, but would require landing over the
anchor to connect, or 2) the tether is within the iTUAV. The iTUAV drops the
tether and the anchor “catches” it to establish the connection. The first
option would require a longer power connection time than the second due to
additional landing and taking-off, while the second option would require a
careful “cable catching” mechanism to bypass environmental factors, such as
strong winds and obstacles. The second option would also require a lightweight
and inexpensive tether design to reduce impact on the UAV’s size, weight,
power and cost. For this matter, industry players, such as VICOR, are
proposing to transfer high voltage over thin and lightweight tethers and to
use small fixed-ratio bus converters within UAVs. Moreover, depending on
whether the iTUAV will be equipped with a very lightweight tether or not, the
challenge is to design automatic hold/release mechanical or electromagnetic
winches and sockets at the stations and/or UAVs. Currently, similar conductive
automatic charging systems are being prototyped for electric vehicles, such as
the DAZEplug, which can inspire equivalent systems for iTUAVs. In addition,
EasyAerial is on the right track with its Raptor UAV, which is capable of
detaching itself from the tether.

  * •

Management of iTUAV operations: The management of UAV operations is an active
area of research a in the context of unmanned aircraft system traffic
management (UTM). For iTUAVs, operations are slightly different since they can
“jump” from one anchor to another and thus induce unpredictable environmental
changes. This aspect should be considered when integrating iTUAV operations
within UTM systems. Also, iTUAV operations may be affected by the deployment
strategy of anchors. For instance, vehicle-mounted anchors may change
location, thus causing iTUAV placement/trajectory updates.

  * •

Integration of iTUAV with 5G and beyond technologies: Although the proposed
iTUAV system offers a tradeoff between the flexibility of UAVs and the
unlimited power of TUAVs, their performance is still suboptimal. To further
enhance iTUAV communications, other technologies can be leveraged, such as
reconfigurable smart surfaces (RISs) and device-to-device (D2D)
communications. Specifically, RIS and D2D can extend the coverage area of an
iTUAV and thus reduce the number of required anchors. Such approaches are
expected to drastically reduce the deployment costs of iTUAV systems.

##  VI Conclusion

With the proliferation of UAV-based applications and the recent development of
TUAVs, iTUAV systems are envisioned in this article as an intermediate
solution that offers a tradeoff between the continuous power supply of TUAVs
and the mobility of UAVs. In this paper, we first provided an overview of UAV-
based communications, including UAV-BSs and TUAVs. Then, we proposed the iTUAV
system and detailed its components, operation mode, and distinguishing
features. Through a case study, we evaluated the coverage performance of the
proposed iTUAV system and compared it to UAV-BS and TUAV counterparts.
Preliminary results demonstrated the potential of iTUAV systems to sustain
long and reliable cellular connectivity missions. However, several issues need
to be addressed before their extensive deployment.

## References

  * [1] M. Alzenad, A. El-Keyi, F. Lagum, and H. Yanikomeroglu, “3-D placement of an unmanned aerial vehicle base station (UAV-BS) for energy-efficient maximal coverage,” _IEEE Wireless Commun. Lett._ , vol. 6, no. 4, pp. 434–437, Aug. 2017.
  * [2] Q. Wu, Y. Zeng, and R. Zhang, “Joint trajectory and communication design for multi-UAV enabled wireless networks,” _IEEE Trans. Wireless Commun._ , vol. 17, no. 3, pp. 2109–2121, Mar. 2018.
  * [3] W. Jaafar, S. Naser, S. Muhaidat, P. C. Sofotasios, and H. Yanikomeroglu, “On the downlink performance of RSMA-based UAV communications,” _IEEE Trans. Veh. Technol._ , vol. 69, no. 12, pp. 16 258–16 263, Dec. 2020.
  * [4] M. Kishk, A. Bader, and M.-S. Alouini, “Aerial base station deployment in 6G cellular networks using tethered drones: The mobility and endurance tradeoff,” _IEEE Veh. Technol. Mag._ , vol. 15, no. 4, pp. 103–111, Sep. 2020.
  * [5] I. Bor-Yaliniz and H. Yanikomeroglu, “The new frontier in RAN heterogeneity: Multi-tier drone-cells,” _IEEE Commun. Mag._ , vol. 54, no. 11, pp. 48–55, Nov. 2016.
  * [6] B. Galkin, J. Kibilda, and L. A. DaSilva, “UAVs as mobile infrastructure: Addressing battery lifetime,” _IEEE Commun. Mag._ , vol. 57, no. 6, pp. 132–137, Jun. 2019.
  * [7] M. Erdelj, O. Saif, E. Natalizio, and I. Fantoni, “UAVs that fly forever: Uninterrupted structural inspection through automatic UAV replacement,” _Ad Hoc Netw._ , vol. 94, p. 101612, Nov. 2019.
  * [8] W. Jaafar and H. Yanikomeroglu, “Dynamics of laser-charged UAVs: A battery perspective,” _IEEE Internet of Things J._ , vol. 8, no. 13, pp. 10 573–10 582, Jul. 2021.
  * [9] M. A. Kishk, A. Bader, and M.-S. Alouini, “On the 3-D placement of airborne base stations using tethered UAVs,” _IEEE Trans. Commun._ , vol. 68, no. 8, pp. 5202–5215, Aug. 2020.
  * [10] N. Tafintsev, D. Moltchanov, M. Gerasimenko, M. Gapeyenko, J. Zhu, S.-p. Yeh, N. Himayat, S. Andreev, Y. Koucheryavy, and M. Valkama, “Aerial access and backhaul in mmwave B5G systems: Performance dynamics and optimization,” _IEEE Commun. Mag._ , vol. 58, no. 2, pp. 93–99, Feb. 2020.
  * [11] G. Castellanos, A. Colpaert, M. Deruyck, E. Tanghe, E. Vinogradov, L. Martens, S. Pollin, and W. Joseph, “Evaluation of beamsteering performance in multiuser MIMO unmanned aerial base stations networks,” _IEEE Access_ , vol. 10, pp. 62 565–62 580, 2022.
  * [12] A. L. Yingst and V. Marojevic, “Tethered UAV with high gain antenna for BVLOS CNPC: A practical design for widespread use,” in _Proc. IEEE Int. Symp. World Wireless Mob. Multim. Net. (WoWMoM)_ , Jul. 2021, pp. 323–328.
  * [13] A. Al-Hourani, S. Kandeepan, and S. Lardner, “Optimal LAP altitude for maximum coverage,” _IEEE Wireless Commun. Lett._ , vol. 3, no. 6, pp. 569–572, Dec. 2014.
  * [14] M. Mirahsan, R. Schoenen, and H. Yanikomeroglu, “HetHetNets: Heterogeneous traffic distribution in heterogeneous wireless cellular networks,” _IEEE J. Sel. Areas Commun._ , vol. 33, no. 10, pp. 2252–2265, Oct. 2015\.
  * [15] N. Cherif, W. Jaafar, H. Yanikomeroglu, and A. Yongacoglu, “On the optimal 3D placement of a UAV base station for maximal coverage of UAV users,” in _Proc. IEEE Glob. Commun. Conf. (Globecom)_ , Taipei, Taiwan, Dec. 2020, pp. 1–6.


# Zero-One laws for random feasibility problems

Dylan J. Altschuler  D.J. Altschuler Department of Mathematical Sciences
Carnegie Mellon University<EMAIL_ADDRESS>
###### Abstract.

We introduce a general random model of a combinatorial optimization problem
with geometric structure that encapsulates both linear programming and integer
linear programming. Let $Q$ be a bounded set called the feasible set, $E$ be
an arbitrary set called the constraint set, and $A$ be a random linear
transform. We define and study the $\ell^{q}$-margin,

$\mathcal{M}_{q}:=d_{\ell^{q}}\left(AQ,E\right)\,.$

The margin quantifies the feasibility of finding $y\in AQ$ satisfying the
constraint $y\in E$. Our contribution is to establish strong concentration of
the $\ell^{q}$-margin for any $q\in(2,\infty]$, assuming only that $E$ has
permutation symmetry. The case of $q=\infty$ is of particular interest in
applications—specifically to combinatorial “balancing” problems—and is
markedly out of the reach of the classical isoperimetric and concentration-of-
measure tools that suffice for $q\leq 2$.

Generality is a key feature of this result: we assume permutation symmetry of
the constraint set and nothing else. This allows us to encode many
optimization problems in terms of the margin, including random versions of:
the closest vector problem, integer linear feasibility, perceptron-type
problems, $\ell^{q}$-combinatorial discrepancy for $2\leq q\leq\infty$, and
matrix balancing. Concentration of the margin implies a host of new sharp
threshold results in these models, and also greatly simplifies and extends
some key known results.

##  1\. Introduction

Balancing covariates in experimental design, sparsifying a graph, and training
a single-layer neural net are seemingly disparate combinatorial optimization
problems. Nonetheless, they as well as a wide range of other problem can be
recast as generalizations of the Closest Vector Problem, a core problem in
integer programming.

> Find the $\ell^{q}$-closest point of a set $Q$ to another set $E$.

This is highly non-trivial for general $Q$ and $E$; crucially, properties like
convexity are not assumed. A natural random model is to take a random linear
transformation of either $Q$ or $E$.

######  Definition 1 (Generalized Random Feasibility).

Let $Q\subset\mathbb{R}^{N}$ and $E\subset\mathbb{R}^{M}$ be sets called the
feasible set and constraint set, respectively. Fix a matrix
$A\in\mathbb{R}^{M\times N}$ with independent standard normal entries. The
$\ell^{q}$-margin $\mathcal{M}_{q}(A):=\mathcal{M}_{q,Q,E}(A)$ is defined as:

$\mathcal{M}_{q}(A):=\min_{\sigma\in Q}d_{\ell^{q}}\left(A\sigma,E\right)\,,$

and the $(A,Q,E)$-feasibility problem is the task of determining if
$\mathcal{M}_{q}$ is zero.

The word margin is chosen in analogy to terminology from the literature of
perceptron models. The margin quantifies the “distance to satisfiability” for
the following program: find $\sigma\in Q$ with $A\sigma\in E$. In this
program, $A$ and $E$ encode a random set of constraints on $Q$, and the margin
$\mathcal{M}_{q}(A)$ measures the least the constraints can be violated by
optimizing over $\sigma\in Q$. In particular, the margin is zero if and only
if this program is feasible. The exponent $q$ controls how heavily the largest
violations are penalized.

In the special case of the feasible set $Q$ being a subset of the integer
lattice and the constraint set $E$ being a rectangle
$[-\infty,b_{1}]\times\dots\dots[-\infty,b_{M}]$ for some vector
$b\in\mathbb{R}^{M}$, we recover the canonical form of random integer linear
feasibility. Namely, the margin is zero if and only if there exists $\sigma\in
Q$ satisfying

$(A\sigma)_{i}\leq b_{i}\,,\quad\forall\,i\in[M]\,.$

If $Q$ is $\mathbb{R}^{N}$ instead, we recover random linear programming.

The technical contribution of this article is strong concentration bounds for
$\mathcal{M}_{q}$ under the assumptions that $E$ has sufficient permutation
symmetry and $Q$ is bounded. Concentration for the margin can be interpreted
as a sharp threshold as follows. Define the $\ell^{q}$-expansion of the
constraint set $E$ by

$E_{\delta}:=\left\\{x\in\mathbb{R}^{M}~{}:~{}d_{q}(x,E)\leq\delta\right\\}\,.$

The $\ell^{q}$-margin is exactly the smallest $\delta$ so that $E_{\delta}\cap
AQ$ is non-empty. Thus, if the margin has fluctuations on some vanishing
scale, then as one expands $E$ with respect to $\ell^{q}$, the probability
that it contains a point of $AQ$ will jump from zero to one in a vanishing
window.

It is worth highlighting that this notion of sharp threshold is non-asymptotic
in an important sense. The dimension is held fixed while $\delta$ is varied.
The existence of a sequence of problems indexed by $N$ or $M$ is not assumed.
In the examples we will introduce shortly, this will be a significant
departure from previous work and a source of increased generality.

###  1.1. Main Results

######  Definition 2.

Say a set $E\subset\mathbb{R}^{n}$ has permutation symmetry if for any
permutation $\pi\in S_{n}$ and $x\in\mathbb{R}^{n}$,

$(x_{1},\dots,x_{n})\in E\quad\text{if and only
if}\quad\left(x_{\pi(1)},\dots,x_{\pi(n)}\right)\in E\,.$

This is a combinatorial notion of regularity. Typical examples include
Cartesian products $E:=(E_{0})^{M}$ or the $\ell^{p}$ unit ball for any $p$.

######  Theorem 1 (Main result: concentration of the margin).

There is a universal constant $C>0$ so the following holds. Let
$Q\subset\mathbb{R}^{N}$ be a subset of the Euclidean unit ball and $E$ have
permutation symmetry. For $q\in[2,\infty]$,

$\mathrm{Var}\left(\mathcal{M}_{q}(A)\right)\leq\frac{C}{1+\left(\frac{1}{2}-\frac{1}{q}\right)\log
M}\,.$ (1.1)

By homogeneity, the assumption that $Q$ is a subset of the unit ball could be
replaced by multiplying the right-hand side of Eq. 1.1 by a factor of
$\max_{\sigma\in Q}\|\sigma\|_{2}^{2}$. At least for $q=\infty$, our result
cannot be improved without further assumptions. Letting $Q$ be a singleton on
the $\ell^{2}(\mathbb{R}^{N})$-unit sphere and $E$ be the origin in
$\mathbb{R}^{M}$ makes this clear (see Chapter 5, section 6 of [20]). However,
Theorem 1 should be seen as an important but purely qualitative improvement
over the trivial bound of $\mathrm{Var}\left(\mathcal{M}_{q}(A)\right)\leq 1$,
which follows from the Gaussian Poincaré inequality (see details in the proof
of Theorem 1). In many of the $(A,Q,E)$-feasibility problems that appear in
actual applications, it should be the case that
$\mathrm{Var}\left(\mathcal{M}_{q}(A)\right)\leq 1/\mathrm{poly}(M)$.

The assumption of permutation symmetry on $E$ is a serious restriction.
Unfortunately, it cannot be completely dropped: letting $Q$ be a singleton and
$E=\mathbb{R}^{M-1}\times[-1,1]$, clearly the fluctuations of the
$\mathcal{M}_{\infty}$ are order one. Nonetheless, it is possible to somewhat
relax the permutation symmetry condition on $E$. The following extension
allows for imposing several different types of constraints on a feasibility
problem.

######  Theorem 2 (Block symmetry suffices).

There is a universal constant $C>0$ so that the following holds. Let
$Q\subset\mathbb{R}^{N}$ be a subset of the Euclidean unit ball and let
$E=E_{1}\times\dots,E_{k}$ where $E_{i}\subset\mathbb{R}^{M_{i}}$ has
permutation symmetry for each $i$ and $\sum_{i=1}^{k}M_{i}=M$. Abbreviate
$m:=\min_{i\in k}M_{i}$. For each $q\in[2,\infty]$,

$\mathrm{Var}\left(\mathcal{M}_{q}(A)\right)\leq
C\left(1+\frac{1}{2}\log\left(\frac{m^{1-\frac{2}{q}}}{k}\vee
1\right)\right)^{-1}\,.$ (1.2)

######  Remark 1.

Let us briefly highlight the generality of Theorems 1 and 2. While there are
permutation symmetry requirements on $E$, there is nearly complete freedom for
$Q$. The feasible set can be discrete, continuous, or even a singleton.
Canonical examples include the sphere, solid cube, discrete cube, bounded
subset of the integer lattice, and arbitrary subsets (such as level-sets of an
arbitrary function) of any of the previous examples. Our results hold without
distinguishing between these situations.

Our main technical tool is Talagrand’s $L^{1}$-$L^{2}$ (Gaussian)
hypercontractive inequality, given below as Lemma 2. There is a long and rich
history of this inequality being used to prove similar sharp thresholds in
various settings. See the expositions of Kalai [35] and Chatterjee [20] for a
wealth of examples in the Boolean and Gaussian settings, respectively. In
particular, our result is similar to the classical theorems of Friedgut and
Bourgain [30] and Friedgut and Kalai [31] that establish a sharp threshold for
any permutation-transitive monotone Boolean function. The assumption of
permutation-transitivity is used in their theorems for the same purpose as in
ours.

###  1.2. Future Directions

Some open problems that seem attractive but quite challenging:

  * Q1.

Obtain polynomial improvements over the given rates in the case that $Q$ has
large cardinality and is well-spread (i.e. the average inner product over all
pairs of elements of $Q$ is bounded away from one). A natural place to start
is the dynamical variance identity given in Lemma 2.1 of [20].

  * Q2.

Explore the quantitative the trade-off between the permutation symmetry of $E$
and the concentration of the margin.

  * Q3.

Extend these results to other disorders for the matrix $A$. Independent
Boolean or Rademacher entries are natural and may be easy. Independent columns
would be quite interesting but potentially harder.

###  1.3. Notation

The phrase “almost every” will always be with respect to the Gaussian or
Lebesgue measure. Since they are mutually absolutely continuous, this is
without ambiguity. We say a function $F:\mathbb{R}^{d}\to\mathbb{R}$ is
$(L,q)$-Lipschitz if $|F(x)-F(y)|\leq L\|x-y\|_{q}$ for all $x$ and $y$. The
set $E$ will always be assumed closed.

##  2\. Applications and Previous Works

###  2.1. Random Integer Programming

Average-case linear programming and integer linear programming have been the
subject of intense study over the past few decades, in large part due to the
enormous gap between worst-case guarantees and average-case empirical
performance of (integer) linear programming algorithms [46, 50, 23]. Much of
the work on integer programming focuses on understanding integrality gaps.
Both the random setting [27, 19, 17, 18] and deterministic setting have been
extensively considered. (The latter is too rich to introduce here; we refer
the reader to [26].) The study of integrality gaps often utilizes the notions
of “sensitivity” and “proximity,” which quantify the distance between the
vertices and lattice points contained in a polytope [5, 22].

Much more closely related are the Shortest Vector Problem (SVP) and Closest
Vector Problem (CVP) [26, 3]. The CVP asks: given a lattice and a target
vector $v$, find $w$ in the lattice minimizing $\|v-w\|_{2}$. The SVP asks the
same with $v=0$ and the origin removed from the lattice. The author is not
aware of work prior to this article on random versions of these problems.

###  2.2. Combinatorial Discrepancy

Combinatorial discrepancy arises as a fundamental quantity in a plethora of
fields including combinatorics, geometry, optimization, information theory,
and experimental design [49, 21, 39]. For an $M\times N$ matrix $A$, the
combinatorial discrepancy $\mathrm{disc}(A)$ is given by

$\mathrm{disc}(A):=\min_{\sigma\in\frac{1}{\sqrt{N}}\left\\{-1,+1\right\\}^{N}}\|A\sigma\|_{\infty}\,.$

There are a number of outstanding open conjectures that seem out of reach of
current tools, motivating much recent interest in random [19, 9, 55, 33, 29,
44, 15, 28, 7, 2, 1, 43, 47, 32] and semi-random models [13, 12, 14, 4]. It is
a general feature in random discrepancy that the second moment method will
yield a coarse threshold [9], but not a sharp threshold (unless $M\ll N$
[55]). The second moment method is generically difficult to improve upon.

However, a recent series of breakthroughs overcame this technical hurdle and
established extremely precise control in the square regime $M\asymp N$.
Perkins and Xu [43] and Abbe, Li, and Sly [2] simultaneously obtained a sharp
threshold for the discrepancy of Gaussian and Rademacher matrices,
respectively, as well as strong control over the number of solutions.
Subsequently, the discrepancy of a Gaussian matrix was shown by the author to
concentrate within a $\mathcal{O}\left(\log(N)/N\right)$ window [6]; the
logarithm has been removed by Sah and Sawhney [47]. The mentioned
breakthroughs all are quite technically involved. Our main theorem recovers a
very simple, direct, and different proof (albeit with a highly non-optimal
rate) of the recently established sharp threshold for discrepancy.

Additionally, we also obtain some truly new results in related settings. A
natural generalization of combinatorial discrepancy, the $\ell^{q}$
discrepancy of a matrix is given by

$\mathrm{disc}_{q}(A):=\min_{\sigma\in\left\\{-1,+1\right\\}^{N}}\|A\sigma\|_{q}\,.$

While $\ell^{q}$ discrepancy has certainly been extensively studied for
deterministic matrices (see e.g. [8, 25] for a list of references; the
literature dates back to at least a question of Dvoretsky in 1960, and is too
vast to introduce here), to the best of our knowledge nothing is known about
the random setting. Similarly to the $q=\infty$ setting, it is natural to
expect the second moment method to yield a coarse threshold. Any such future
result can be automatically upgraded to a sharp threshold by applying our main
result:

######  Theorem 3 (Sharp threshold for $\ell^{q}$ discrepancy).

Let $A\in\mathbb{R}^{N\times N}$ with independent standard normal entries and
$2\leq q\leq\infty$. Then:

$\frac{\mathbb{E}\left[\mathrm{disc}_{q}(A)\right]}{\sqrt{\mathrm{Var}\left(\mathrm{disc}_{q}(A)\right)}}\geq\Omega\left(N^{\frac{1}{q}}\sqrt{1+\left(\frac{1}{2}-\frac{1}{q}\right)\log
N}\right)\,.$

###### Proof.

The variance of $\mathcal{M}_{q}$ can be upper-bounded by applying Theorem 1
with $E=\left\\{0\right\\}$ and $Q$ the normalized discrete cube
$N^{-1/2}\left\\{-1,+1\right\\}^{N}$. The expectation of $\mathcal{M}_{q}$ is
lower-bounded by $N^{1/q}$ via a simple application of Markov’s inequality.

Indeed, it suffices to show that for all $\sigma\in Q$ that
$\mathbb{P}\left[\|A\sigma\|_{q}<cN^{1/q}\right]<2^{-(1+c^{\prime})N}$. For a
particular $\sigma$, we have $A\sigma=:Y$ is distributed as a standard normal
in $\mathbb{R}^{M}$. Let $\mathcal{G}$ denote the event that at least
$\epsilon n$ entries of $Y$ are greater than $1$. On the event $\mathcal{G}$,
we have $\|A\sigma\|_{q}\geq\epsilon^{1/q}N^{1/q}$. Standard tail bounds for
the binomial distribution yield

$\mathbb{P}\left[\mathcal{G}^{c}\right]\leq\exp\left\\{-\left|\Omega\left(N\epsilon\log(1/\epsilon)\right)\right|\right\\}\leq
2^{-2N}\,,$

where the second inequality follows by taking $\epsilon$ sufficiently small.
Taking $c=\epsilon^{1/q}$ and $c^{\prime}=1$, we are done. ∎

The result and proof remain essentially unchanged if we optimize discrepancy
over any of the feasible sets given in Remark 1 rather than taking $Q$ as the
discrete hypercube. For example, another natural problem for which, to the
best of our knowledge, there are no published results is the relaxation of
random discrepancy to the sphere rather than the discrete cube. This is
analogous to the relaxation of “Ising” spin glasses to “spherical” spin
glasses in statistical physics.

######  Theorem 4 (Sharp threshold for the symmetric spherical perceptron).

For any $q\in[2,\infty]$ and $\alpha\in(0,\infty)$, let
$A\in\mathbb{R}^{\alpha N\times N}$ have iid standard normal entries.

$\mathrm{Var}\left(\min_{\sigma\in
S^{N-1}}\|A\sigma\|_{q})\right)=\mathcal{O}\left(\frac{1}{1+\left(\frac{1}{2}-\frac{1}{q}\right)\log
N}\right)\,.$

It seems reasonable to expect the second moment method to yield a coarse
threshold in this setting as well, which can thus be automatically promoted to
a sharp threshold.

We also note a related work of Minzer, Sah, and Sawhney [41] that appeared
during the writing of this article. They use the Boolean version of
Talagrand’s $L^{1}$-$L^{2}$ inequality to establish a sharp threshold in the
“perfectly friendly bisection” problem. They note that their methods can be
used to show concentration of random $\ell^{\infty}$ discrepancy with
Bernoulli disorder.

###  2.3. Perceptron Models

The Binary Perceptron problem is an enduring model of the classification power
of a single-layer neural net. First introduced in the 1960’s, it remains a
fascinating yet stubborn source of open problems. The binary perceptron is
exactly the $(A,Q,E)$-feasibility problem with parameters:

$q=\infty\,,\quad Q=N^{-1/2}\left\\{-1,+1\right\\}^{N}\,,\quad
E=[K,\infty)^{\alpha N}$

In the literature surrounding the perceptron, the following approach is taken:
fix $K$ and ask for the largest $\alpha$, called the capacity, such that the
above problem is feasible. This exploits the fact that there is a natural
sequence of problems indexed by $\alpha$. Namely, add independent rows to $A$
and extend $E$ by taking Cartesian products with more copies of $[K,\infty)$.
Concretely, the capacity $\bm{\alpha_{*}}$ is the random variable

$\max\left\\{\alpha:\exists\sigma\in Q,~{}\left\langle
A_{i},\sigma\right\rangle>0,\quad\forall i\in[\alpha N]\right\\}\,,$

where $A_{i}$ is the $i$’th row of $A$. Concentration of $\bm{\alpha_{*}}$ was
shown somewhat recently in two impressive and technically involved works [56,
42]. Xu used the Fourier-analytic pseudo-junta theorem of Hatami to show
concentration of $\bm{\alpha_{*}}$, establishing the first sharp threshold
result for the perceptron [56]. Subsequently, Nakajima and Sun established a
sharp threshold for a wide variety of related models [42]; their methods
extend some prior work of Talagrand [52, 54]. The generalization studied by
Nakajima and Sun corresponds to letting $E:=(E_{0})^{\alpha N}$, where $E$ can
be any set that satisfies a mild structural assumption111We will not make this
precise. See Assumption 1.2 and Theorem 1.2 of [42] for the full statement..
In our notation, previous work can be summarized as:

######  Theorem 5 (Sharp threshold for the capacity of the generalized
perceptron [56, 42]).

Let $q=\infty$, $Q=\left\\{-1,+1\right\\}^{N}$ and
$E_{\alpha}:=(E_{0})^{\alpha N}$. Then there exists some sequence
$a_{c}:=a_{c}(N,E_{0})$ such that: for any $\epsilon>0$ and $N$ sufficiently
large, the $(A,Q,E_{\alpha})$-feasibility problem is satisfiable with high
probability for $\alpha<a_{c}-\epsilon$ and unsatisfiable with high
probability for $\alpha>a_{c}+\epsilon$.

We take a dual approach: fix an $\alpha$, and look for the largest $K$ so that
there exists $\sigma\in Q$ with $A\sigma\in E$. Applying Theorem 1 readily
recovers a similar sharp threshold in the parameter $K$. Additionally, we gain
a signficant increase in the generality of the constraint sets. As previously
mentioned, our notion of sharp threshold for the margin is non-asymptotic; it
is well-defined for a fixed dimension. Thus we need not assume that $E$ has
product structure $(E_{0})^{\alpha N}$. Instead, we only need $E$ to be
permutation invariant. (For example: the $\ell^{2}$-unit sphere is permutation
invariant but not a product set). Recall the notation $E_{\delta,q}$ for the
$\ell^{q}$-metric expansion of the set $E$,

$E_{\delta}:=\left\\{x\in\mathbb{R}^{\alpha
N}~{}:~{}d_{\infty}(x,E)\leq\delta\right\\}\,.$

Our result is the following immediate consequence of Theorem 1:

######  Theorem 6 (Sharp threshold for the margin of the generalized
perceptron).

Let $2<q\leq\infty$, $Q$ be a feasible set and $E$ be permutation invariant.
Then there exists some sequence $K_{c}:=K_{c}(N)$ such that: for any
$\epsilon>0$ and $N$ sufficiently large, the $(A,Q,E_{K})$-feasibility problem
is unsatisfiable with high probability for $K<K_{c}-\epsilon$ and satisfiable
with high probability for $K>K_{c}+\epsilon$.

Note that the setting considered here is a significant generalization of the
setting of Theorem 5. Not only do we allow for permutation-invariant
constraint sets rather than just product sets, we also are able to take $Q$ as
e.g. the sphere. While the positive spherical perceptron is already well-
understood [48, 53, 54], to the best of our knowledge a sharp threshold result
was not previously known for the negative spherical perceptron. (The
“positive” and ”negative” spherical perceptron refer to parameter regimes for
$\alpha$ for which $K_{c}$ is positive or negative, respectively. The negative
perceptron is conjectured to exhibit a property called “full replica symmetry
breaking”, which makes it difficult to analyze.)

A natural question is whether these two different notions of sharp threshold
considered in Theorem 5 and Theorem 6 coincide when they are both defined—i.e.
when $E=(E_{0})^{\alpha N}$ for some $E\subset\mathbb{R}$. Very loosely
speaking, if $K_{c}$ and $\bm{\alpha_{*}}$ are of the same order, then a sharp
threshold and a sharp threshold in the capacity are equivalent. This is called
the “proportional regime” in constraint satisfaction literature. For the
familiar reader, a slightly more precise statement: the log-number of
satisfying $\sigma$ needs to decrease at asymptotically the same rate if we
add $\delta N$ new constraints or decrease $K$ by $-\delta$, for any positive
constant $\delta$. A formal and rigorous statement of this is available in the
special case of $Q=N^{-1/2}\left\\{-1,+1\right\\}^{N}$ and $E_{0}=[-K,K]$,
given by Lemma 3.2 of [6].

We conclude with a final generalization: Theorem 2—the extension of our main
theorem to block-symmetric constraint sets—immediately yields a sharp
threshold for the margin of perceptron problems with “random labels,” such as
the model raised in [36]. This corresponds to a feasibility problem with
constraint set $E=\left(E_{0}\right)^{M_{1}}\times(E_{0}^{c})^{M-M_{1}}$ and
$M_{1}\asymp M$.

###  2.4. Matrix Balancing

The “Matrix Spencer” conjecture of R. Meka asks the following: given $N$
symmetric matrices $A_{1},\dots,A_{N}$ of dimension $d\times d$, each of
operator norm at most one, determine the feasibility of finding
$\sigma\in\frac{1}{\sqrt{N}}\left\\{-1,1\right\\}^{N}$ such that

$\left\|\sum_{i}\sigma_{i}A_{i}\right\|_{\mathrm{op}}\leq 1\,.$

This problem has interesting applications to quantum comunication complexity
[34] and graph sparsification [16, 45]. There has been some recent progress
[38, 11, 34, 24] in the low-rank setting. Very recently, the random version of
this problem has been considered; a lower bound by the first moment method is
given in Theorem 1.13 of [37]. Due to the extremely strong lower-tail
concentration of the operator norm of a GOE, the main regime of interest is
$N\asymp d^{2}$. Only when $N$ is at least this large does optimizing over
$\sigma$ allow $\|\sum_{i}\sigma_{i}A_{i}\|$ to be changed to first order;
conversely, if $N$ is much larger, the discrepancy will be vanishing [10].

######  Theorem 7 (Sharp threshold for matrix balancing).

Let $A_{1},\dots,A_{N}$ be $d\times d$ GOE matrices, and define

$\mathrm{disc}(A_{1},\dots,A_{N}):=\min_{\sigma\in
N^{-1/2}\left\\{-1,+1\right\\}^{N}}\frac{1}{\sqrt{d}}\left\|\sum\sigma_{i}A_{i}\right\|_{\mathrm{op}}\,.$

Then, for $N\asymp d^{2}$,

$\frac{\mathbb{E}\left[\mathrm{disc}(A_{1},\dots,A_{N})\right]}{\sqrt{\mathrm{Var}\left(\mathrm{disc}(A_{1},\dots,A_{N})\right)}}\geq\Omega\left(\sqrt{d}~{}\right)\,.$
(2.1)

The proof is deferred to the end of the next section. Matrix balancing can be
seen as an integer feasibility problem as follows: flatten each matrix $A_{i}$
into a $d^{2}\times 1$ column vector. And let $A=(A_{1},\dots,A_{N})$. Let the
constraint set $E\subset\mathbb{R}^{d^{2}}$ be the flattening of the $d\times
d$ operator norm ball, and let $Q$ be the discrete cube
$N^{-1/2}\left\\{-1,+1\right\\}^{N}$. However, matrix balancing is not easily
quantified in terms of the $\ell^{q}$-margin and does not quite fit nicely
into the framework of Theorem 1 for two reasons. First, $E$ does not have much
permutation symmetry since the operator norm of a matrix is only invariant
under permuting rows or columns, not arbitrary entries. Second, Theorem 1
would give results on the distance to $E$ in terms of entry-wise norms of the
matrix $M$, which is not quite right. Nonetheless, the ideas behind the proof
of Theorem 1 are extremely general and easy modifications suffice here.

##  3\. Preliminaries

Before proving our main theorems, we introduce our main tools as well as some
technical observations that will help us apply it. We begin with the
celebrated Gaussian Poincaré inequality.

######  Lemma 1 (Gaussian Poincaré).

Let $n$ be finite, $f:\mathbb{R}^{n}\to\mathbb{R}$ be an absolutely continuous
function, and $\gamma^{n}$ denote the standard Gaussian measure on
$\mathbb{R}^{n}$.

$\mathrm{Var}\left(f\right)\leq\mathbb{E}_{\gamma^{n}}\left[\|\nabla
f\|_{2}^{2}\right]\,.$

The Gaussian Poincaré inequality is often quite useful, but sometimes fails to
give optimal rates. In his influential monograph [20], Chatterjee gives the
name “superconcentration” to the variance of a random variable being far
smaller than the Poincaré inequality implies. Chatterjee also shows the
equivalence of superconcentration to the fascinating properties of “chaos” and
“multiple valleys.” It remains a major open problem in this area to establish
general methods for providing polynomial improvements over the Gaussian
Poincaré inequality. However, there is a general tool for obtaining
logarithmic improvements:

######  Lemma 2 (Talagrand’s $L^{1}$-$L^{2}$ inequality; Theorem 5.1 of [20]).

There is some constant $C$ so that the following holds. Let $\gamma^{n}$ be
the Gaussian measure on $\mathbb{R}^{n}$ for any $n$, and
$f:\mathbb{R}^{n}\to\mathbb{R}$ any absolutely continuous function.

$\mathrm{Var}\left(f\right)\leq
C\sum_{i=1}^{n}\|\partial_{i}f\|_{L^{2}(\gamma^{n})}^{2}\left(1+\log\left(\frac{\|\partial_{i}f\|_{L^{2}(\gamma^{n})}}{\|\partial_{i}f\|_{L^{1}(\gamma^{n})}}\right)\right)^{-1}\,.$
(3.1)

In particular,

$\mathrm{Var}\left(f\right)\leq
C\left(\sum_{i=1}^{n}\|\partial_{i}f\|_{L^{2}(\gamma^{n})}^{2}\right)\left(1+\frac{1}{2}\log\left(\frac{\sum_{i}\|\partial_{i}f\|_{L^{2}(\gamma^{n})}^{2}}{\sum_{i}\|\partial_{i}f\|_{L^{1}(\gamma^{n})}^{2}}\right)\right)^{-1}\,.$
(3.2)

The usual formulation of Talagrand’s inequality is Eq. 3.1. Here, Eq. 3.2 will
be more convenient for us. It readily follows from Eq. 3.1 by applying
Jensen’s inequality to the function $g(x)=(1+\log(x)/2)^{-1}$, which is
concave on $(0,1)$. The details can be found in the proof of Theorem 5.4 of
[20].

Talagrand’s inequality is based on hypercontractivity—a way of quantifying the
extreme smoothing properties of the heat flow. Roughly speaking, the Poincaré
inequality can fail to yield optimal rates because it forces a heavy quadratic
penalty on values of $X$ where $f$ has large derivative, even if the Gaussian
measure assigns little mass to these locations. Hypercontractivity allows for
mitigation of this penalty.

We plan to apply Talagrand’s inequality to the variance of the margin. This
requires differentiating the margin. Since the margin is defined in terms of a
distance between two sets, this will consist of two tasks. First,
interchanging a derivative and an infimum. Second, differentiating the
$\ell^{q}$ distance. The former will be accomplished by the classical
“envelope theorem” of Milgrom and Segal (Theorem 1 in [40]).

######  Lemma 3 (Envelope Theorem).

Let $f(x,A)$ be a map $f:X\times[0,1]\to\mathbb{R}$ where $X$ is a subset of
$\mathbb{R}^{n}$. Define the value function

$V(t):=\sup_{x\in X}f(x,t)\,.$

For any $t\in(0,1)$ and any $x^{*}\in\arg\max_{x\in X}f(x,t)$, if
$V^{\prime}(t)$ and the partial derivative $f_{t}(x^{*},t)$ both exist,

$V^{\prime}(t)=f_{t}(x^{*},t)\,.$

For the latter task of differentiating the $\ell^{q}$ distance, we collect
some easy regularity results on $\ell^{q}$ distances. In what follows, let
$E\subset\mathbb{R}^{m}$ be an arbitrary closed set and define

$f_{q}(x):=d_{q}(x,E)\,.$

Recall our notation that a function $F:\mathbb{R}^{M}\to\mathbb{R}$ is called
$(L,q)$-Lipschitz if it is Lipschitz continuous with constant $L$ with respect
to $\ell^{q}$ perturbations to the input.

######  Proposition 1.

Fix $q\in[2,\infty)$ and a non-empty set $E\subset\mathbb{R}^{M}$. Let
$f_{q}(x):=d_{q}(x,E)$ be the $\ell^{q}$ distance between $x$ and $E$.

  * •

$f_{q}$ is $(1,q)$-Lipschitz continuous everywhere.

  * •

$f_{q}$ is absolutely continuous everywhere and continuously differentiable
for Lebesgue a.e. $x$.

  * •

Let $x$ be a point of differentiability for $f_{q}(x)$. Then there is a unique
$\ell^{q}$-projection of $x$ onto $E$; denote it by $z$. Letting $v:=x-z$ and
$i\in[M]$, we additionally have:

$\left|\left(\nabla
f_{q}(x)\right)_{i}\right|=\frac{|v_{i}|^{q-1}}{\|v\|_{q}^{q-1}}\,.$

These are standard facts, but we give a proof for completeness.

###### Proof of Proposition 1.

Let $z\in E$ be arbitrary and let $x$ and $y$ be outside $E$. Fix $q\geq 2$
and set $d:=d_{q}$. By triangle inequality,

$d(x,E)\leq d(x,z)\leq d(x,y)+d(y,z)\,.$

Taking an infimum over $z\in E$ yields $d(x,E)-d(y,E)\leq d(x-y)$. Reversing
the roles of $x$ and $y$ yields a symmetric bound, completing the proof of the
first claim.

By equivalence of norms (i.e. since $\ell_{q}\leq\ell_{2}\leq\sqrt{N}\ell_{q}$
for any $q\in[2,\infty]$), we have that $f_{q}$ is Lipschitz continuous with
respect to the Euclidean norm. This implies a.e. differentiability by
Rademacher’s theorem, as well as absolute continuity everywhere. Continuity of
the derivative will follow by explicit computation.

Let $x$ be a point of differentiability of $f_{q}$ and $y$ be an
$\ell^{q}$-metric projection of $x$ onto $E$. By definition of the derivative,
there exists a unique vector $v$ such that for $w$ sufficiently near $x$,

$f_{q}(w)-f_{q}(x)=v\cdot(w-x)+\mathrm{o}\left(\|w-x\|\right)\,.$ (3.3)

Since we just showed $f_{q}$ is $(1,q)$-Lipschitz, then $\|v\|_{q^{*}}\leq 1$
where $q^{*}$ is the conjugate exponent to $q$. Letting $w=x+\epsilon(y-x)$,
we obtain by homogeneity of the $\ell^{q}$ norm

$\displaystyle|f_{q}(w)-f_{q}(x)|$ $\displaystyle=\epsilon\|y-x\|_{q}\,.$

Rearranging Eq. 3.3,

$|v\cdot(w-x)|=\epsilon\|y-x\|_{q}+\mathrm{o}\left(\epsilon\right)\,.$ (3.4)

Since $\|v\|_{q^{*}}\leq 1$, we have by Hölder’s inequality

$|v\cdot(w-x)|\leq\|w-x\|_{q}\|v\|_{q^{*}}=\epsilon\|y-x\|_{q}\|v\|_{q^{*}}\leq\epsilon\|y-x\|_{q}\,.$
(3.5)

But, Eq. 3.4 shows that Hölder’s inequality Eq. 3.5 actually holds with
equality, up to some vanishing error. For $q<\infty$, it is a standard fact
[51] that this implies

$|v_{i}|=\frac{|y-x|_{i}^{q-1}}{\|y-x\|_{q}^{q-1}}\,.$

In summary, given a projection $y$ of $x$ onto $E$, we can explicitly solve
for the derivative. It is clear that if there is another projection
$y^{\prime}\neq y$, this would contradict the uniqueness of $v$. With the
formula for the derivative of $f_{q}$ established, continuity of the
derivative is now clear by inspection. ∎

Although similar statements hold for $q=\infty$, there is a lack of uniqueness
of the projection onto $E$, which makes direct analysis more
difficult—although definitely still possible. We sidestep this issue with the
standard approach of simply taking $q$ large. Let us make this precise.

######  Proposition 2.

Let $X$ and $Y$ be random variables with finite second moments. Then:

$\mathrm{Var}\left(X+Y\right)\leq
2\left(\mathrm{Var}\left(X\right)+\mathrm{Var}\left(Y\right)\right)$ (3.6)

and

$\mathrm{Var}\left(X\right)\leq
2\left(\mathbb{E}\left[|X-Y|^{2}\right]+\mathrm{Var}\left(Y\right)\right)$
(3.7)

###### Proof.

Both are trivial consequences of the inequality $(a+b)^{2}\leq
2(a^{2}+b^{2})$, valid for all real $a$ and $b$. ∎

######  Proposition 3.

For any $q\geq\log(M)^{2}$, we have

$\mathcal{M}_{\infty}=\mathcal{M}_{q}\left(1+\mathcal{O}\left(\frac{1}{\log
M}\right)\right)\,.$

In particular, combining Proposition 2 and Proposition 3 will allow us to
study the variance of $\mathcal{M}_{\infty}$ via the variance of
$\mathcal{M}_{\log(N)^{2}}$, which is easier to differentiate due to
Proposition 1. We omit the proof of Proposition 3 since it is an immediate
application of the classical fact:

$\|\cdot\|_{\infty}=\|\cdot\|_{q}\left(1+\mathcal{O}\left(\frac{1}{\log
M}\right)\right)\,.$

We conclude our preliminary discussion by illustrating the utility of the
Poincaré inequality with a quick proof of Theorem 7, the sharp threshold for
random matrix balancing problem. The following classical fact is needed.

######  Lemma 4.

Let $A$ be a symmetric matrix of full rank with distinct eigenvalues. Let
$\lambda$ be the largest eigenvalue and let $u$ be the corresponding unique
eigenvector of unit norm.

$\frac{\partial}{\partial A_{ij}}\lambda=u_{i}u_{j}$ (3.8)

###### Proof of Lemma 4.

Implicitly differentiate the formula

$Au=\lambda u\,,$

and then left multiply by $u^{t}$. Using that $u^{t}du=(d\|u\|_{2}^{2})/2=0$,
and then using symmetry of $A$ so that $u^{t}A=\lambda u^{t}$, we obtain the
result. ∎

###### Proof of Theorem 7.

We apply the classical Gaussian Poincaré inequality to $\mathrm{disc}(A)$.
Clearly the operator norm of $\sum A_{i}\sigma_{i}$ for a particular $\sigma$
is Lipschitz in $A$, and thus so is $\mathrm{disc}(A)$. By Rademacher’s
theorem, both are then differentiable for almost every $A$. So, applying Lemma
3, for almost every $A$ there is a vector $\sigma^{*}$ with
$\mathrm{disc}(A)=\|\sum_{i}\sigma^{*}_{i}A_{i}\|$ and

$\nabla\mathrm{disc}(A)=\frac{1}{\sqrt{d}}\nabla\left\|\sum\sigma_{i}^{*}A_{i}\right\|_{\mathrm{op}}=\left(u_{i}^{*}u_{j}^{*}\right)_{i,j\in[d]}\,.$

Here, $u^{*}$ denotes the (unit) eigenvector associated with the top
eigenvalue of $\sum\sigma^{*}_{i}A_{i}$. Then:

$\displaystyle\mathrm{Var}\left(\mathrm{disc}(G)\right)\leq\frac{1}{d}~{}\mathbb{E}\left[\|\nabla\mathrm{disc}(G)\|_{2}^{2}\right]=\frac{1}{d}~{}\|u^{*}\|_{2}^{4}=\frac{1}{d}\,.$

This is far from sharp and can easily be improved, even polynomially. But it
suffices for a sharp threshold. This concludes the upper bound on the
variance. The lower bound that $\mathrm{disc}(G)\geq\Omega\left(1\right)$
follows from a first moment method (see Theorem 1.13 of [37]). ∎

##  4\. Concentration of the margin

###### Proof of Theorem 1.

By Proposition 3 in conjunction with Proposition 2, we may assume without loss
of generality that $q\leq\log(M)^{2}$. In particular, $q$ is finite (but
possibly $M$-dependent).

Let us verify the differentiability of the margin. Define the function
$g(A,\sigma)=d(A\sigma,E)$. For any matrix $B\in\mathbb{R}^{M\times N}$, we
have by triangle inequality:

$\displaystyle\left|g(A,\sigma)-g(B,\sigma)\right|$ $\displaystyle\leq
d_{q}(A\sigma,B\sigma)$ $\displaystyle\leq\|A-B\|_{2,q}\|\sigma\|_{2}$
$\displaystyle\leq\|A-B\|_{2,q}\,.$

The final inequality follows from the theorem assumption that the feasible set
is bounded in $\ell^{2}(\mathbb{R}^{N})$. By equivalence of matrix norms, we
have that $g$ is $\ell^{2}$-Lipschitz with some finite (possibly
$N$-dependent) constant. By Rademacher’s theorem, $\nabla_{A}g(A,\sigma)$
exists for almost every $A$.

Similarly, the margin is also Lipschitz and thus differentiable for almost
every $A$. Indeed, by triangle inequality:

$\displaystyle|\mathcal{M}_{q}(A)-\mathcal{M}_{q}(B)|\leq\sup_{\sigma\in
Q}\|A\sigma-B\sigma\|_{q}\leq\|A-B\|_{2,q}\,.$

By Proposition 1 and the chain rule, we have for each $\sigma\in Q$ and almost
every $A$ the identity:

$\left|\partial_{A_{ij}}g(A,\sigma)\right|=|\sigma_{j}|\frac{|v_{i}|^{q-1}}{\|v\|_{q}^{q-1}}\,,\quad\forall~{}i\in[M],~{}j\in[N]$
(4.1)

where $z$ is the unique $\ell^{q}$-projection of $A\sigma$ onto $E$ and
$v=A\sigma-z$. So, for almost every $A$ and any $\sigma^{*}$ with
$g(A,\sigma^{*})=\mathcal{M}(A)$, Lemma 3 yields:

$\nabla\mathcal{M}(A)=\left(|\sigma_{j}^{*}|\frac{|v_{i}|^{q-1}}{\|v\|_{q}^{q-1}}\right)_{i\in[M],~{}j\in[N]}\,.$

Here $v$ again denotes the unique $\ell^{q}$ projection of $A\sigma^{*}$ onto
$E$.

We turn to bounding the variance of $\mathcal{M}_{q}$ using Talagrand’s
$L^{1}$-$L^{2}$ inequality. The quantities involved in Eq. 3.2 of Lemma 2 are:

$\displaystyle a_{ij}^{2}$
$\displaystyle:=\mathbb{E}\left[\left|\partial_{A_{ij}}\mathcal{M}_{q,E}(A)\right|\right]^{2}$
$\displaystyle b_{ij}^{2}$
$\displaystyle:=\mathbb{E}\left[\left|\partial_{A_{ij}}\mathcal{M}_{q,E}(A)\right|^{2}\right]\,.$

By Hölder’s inequality, the $q$ and $(q-1)$ norm of $v$ cannot be too far
apart:

$\|v\|_{q}^{q-1}\leq\|v\|_{q-1}^{q-1}\leq\left(M\right)^{\frac{1}{q}}\|v\|_{q}^{q-1}\,.$
(4.2)

Additionally, by permutation-invariance of the constraint set $E$,

$a_{ij}^{2}=\mathbb{E}\left[\left|\sigma_{j}^{*}\right|\frac{|v_{i}|^{q-1}}{\|v\|_{q}^{q-1}}\right]^{2}=\left(\frac{1}{M}~{}\mathbb{E}\left[\left|\sigma_{j}^{*}\right|\frac{\|v\|_{q-1}^{q-1}}{\|v\|_{q}^{q-1}}\right]\right)^{2}\,.$
(4.3)

Combining Eq. 4.2 and Eq. 4.3,

$\displaystyle\sum_{ij}a_{ij}^{2}$
$\displaystyle=\frac{1}{M}\sum_{j}~{}\mathbb{E}\left[\left|\sigma_{j}^{*}\right|\frac{\|v\|_{q-1}^{q-1}}{\|v\|_{q}^{q-1}}\right]^{2}\leq
M^{\frac{2}{q}-1}\sum_{j}~{}\mathbb{E}\left[\left|\sigma_{j}^{*}\right|\right]^{2}=M^{\frac{2}{q}-1}\mathbb{E}\left[\|\sigma^{*}\|_{2}^{2}\right]\leq
M^{\frac{2}{q}-1}\,.$ (4.4)

The last inequality follows from the assumption that the feasible set is
bounded. By monotonicity of $\ell^{p}$ norms, we also have

$\displaystyle\sum_{ij}b_{ij}^{2}$
$\displaystyle=\sum_{j}~{}\mathbb{E}\left[\left|\sigma_{j}^{*}\right|^{2}\left(\frac{\|v\|_{2(q-1)}}{\|v\|_{q}}\right)^{2(q-1)}\right]\leq\sum_{j}~{}\mathbb{E}\left[\left|\sigma_{j}^{*}\right|^{2}\right]\leq
1\,.$ (4.5)

Finally, it is readily checked that for any $a>0$, the following is monotone
increasing in $x$ on $[a^{-1},\infty)$:

$f(x)=\frac{x}{1+\frac{1}{2}\log(ax)}\,.$

By Jensen’s inequality and Eq. 4.5, we have
$\sum_{ij}a_{ij}^{2}\leq\sum_{ij}b_{ij}^{2}\leq 1$. So, (in order of the
inequalities below) applying Eq. 3.2 of Lemma 2, then monotonicity of $f$, and
then Eq. 4.4 yields:

$\displaystyle\mathrm{Var}\left(\mathcal{M}_{q}\right)\leq\frac{C\sum_{ij}b_{ij}^{2}}{1+\frac{1}{2}\log\left(\frac{\sum_{ij}b_{ij}^{2}}{\sum_{ij}a_{ij}^{2}}\right)}\leq\frac{C}{1+\frac{1}{2}\log\left(\frac{1}{\sum_{ij}a_{ij}^{2}}\right)}\leq\frac{C}{1+\frac{1}{2}\log\left(M^{1-\frac{2}{q}}\right)}\,.$

∎

######  Remark 2.

The reason that it works to apply Hölder’s inequality so crudely is the
following dichotomy: we are already done by Poincaré if
$\sum_{ij}b_{ij}^{2}\ll 1$. On the other hand, if $\sum_{ij}b_{ij}^{2}\approx
1$ then the $q$ and $2(q-1)$ norms of $v$ are not very far apart, so $v$ must
be a highly structured vector, in which case the $q$ and $q-1$ norms of $v$
must also be comparable. Then $b^{2}\gg a^{2}$ and Talagrand’s inequality
easily yields a logarithmic improvement.

###### Proof of Theorem 2.

We adopt the notation and proof of Theorem 1. The first section on
differentiability of the margin remains unchanged. Partition $[M]$ into
$I_{1},\dots,I_{k}$ so that $|I_{j}|=M_{j}$ by setting $I_{1}=[M_{1}]$,
$I_{2}=\left(M_{1}+1,\dots,M_{1}+M_{2}\right)$, and so on. Let
$w_{1}:=v_{I_{1}}$ be the $M_{1}$-dimensional vector induced by taking the
subset of $v$ with indices in $I_{1}$. Define $w_{j}:=v_{I_{j}}$ similarly.
Then the concatenation $(w_{1},\dots w_{k})$ is simply $v$. Arguing as in the
proof of Theorem 1, it is easy to check by permutation symmetry:

$\displaystyle\sum_{i\in
I_{t}}\sum_{j}a_{ij}^{2}=\frac{1}{M_{t}}\sum_{j}\mathbb{E}\left[|\sigma^{*}_{j}|\left(\frac{\|w^{(t)}\|_{(q-1)}}{\|v\|_{q}}\right)^{(q-1)}\right]^{2}\leq
M_{t}^{\frac{2}{q}-1}\sum_{j}\mathbb{E}\left[|\sigma^{*}_{j}|\left(\frac{\|w^{(t)}\|_{q}}{\|v\|_{q}}\right)^{(q-1)}\right]^{2}\leq
M_{t}^{\frac{2}{q}-1}\,.$

Note that by Jensen’s inequality $\sum_{ij}b_{ij}^{2}\geq\sum_{ij}a_{ij}^{2}$
always. Thus, by Eq. 3.2 of Lemma 2, we have:

$\displaystyle\mathrm{Var}\left(\mathcal{M}_{q}\right)$ $\displaystyle\leq
C\left(\sum_{ij}b_{ij}^{2}\right)\left(1+\frac{1}{2}\log\left(\frac{\sum_{ij}b_{ij}^{2}}{\sum_{ij}a_{ij}^{2}}\vee
1\right)\right)^{-1}$ $\displaystyle\leq
C\left(1+\frac{1}{2}\log\left(\frac{1}{\sum_{t=1}^{k}M_{t}^{\frac{2}{q}-1}}\vee
1\right)\right)^{-1}$ $\displaystyle\leq
C\left(1+\frac{1}{2}\log\left(\frac{\left(\min_{t\in[k]}M_{t}\right)^{1-\frac{2}{q}}}{k}\vee
1\right)\right)^{-1}\,.$

From the first to the second line we have used monotonicity in $x$, for any
$a>0$ and all $x\in\mathbb{R}$, of the function

$f(x)=\frac{x}{1+\frac{1}{2}\log(ax\vee 1)}\,.$

∎

## Acknowledgments

I am deeply grateful to Jonathan Niles-Weed for invaluable support, advice,
and mentorship throughout all stages of this project. I also benefited from
useful and encouraging conversations with Paul Bourgade, Guy Bresler, Brice
Huang, Mark Sellke, Joel Spencer, Nike Sun, Konstantin Tikhomirov, and Will
Perkins during the long exploratory phase of this project. Finally, the
monograph [20] of Chatterjee was an important source of inspiration for this
work. This article is adapted from a chapter of the author’s dissertation at
NYU and was supported by a MacCracken fellowship, an NSF GRFP grant, and NSF
grant DMS-2015291.

## References

  * [1] Abbe, E., Li, S., and Sly, A. Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster.  In STOC ’22—Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing ([2022] ©2022), ACM, New York, pp. 860–873.
  * [2] Abbe, E., Li, S., and Sly, A. Proof of the contiguity conjecture and lognormal limit for the symmetric perceptron.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science—FOCS 2021. IEEE Computer Soc., Los Alamitos, CA, [2022] ©2022, pp. 327–338.
  * [3] Aggarwal, D., Dadush, D., and Stephens-Davidowitz, N. Solving the closest vector problem in $2^{n}$ time—the discrete Gaussian strikes again!  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015. IEEE Computer Soc., Los Alamitos, CA, 2015, pp. 563–582.
  * [4] Aigner-Horev, E., Hefetz, D., and Trushkin, M. Smoothed analysis of the Komlós conjecture: Rademacher noise.  arXiv preprint arXiv:2307.06285 (2023).
  * [5] Aliev, I., Henk, M., and Oertel, T. Distances to lattice points in knapsack polyhedra.  Mathematical Programming 182, 1-2 (2020), 175–198.
  * [6] Altschuler, D. J. Critical window of the symmetric perceptron.  Electronic Journal of Probability (to appear) (2023).
  * [7] Altschuler, D. J., and Niles-Weed, J. The discrepancy of random rectangular matrices.  Random Structures & Algorithms (2021).
  * [8] Ambrus, G., and Bozzai, R. Colorful vector balancing.  arXiv preprint arXiv:2302.10865 (2023).
  * [9] Aubin, B., Perkins, W., and Zdeborová, L. Storage capacity in symmetric binary perceptrons.  J. Phys. A 52, 29 (2019), 294003, 32.
  * [10] Bandeira, A., and Maillard, A. personal communication.
  * [11] Bansal, N., Jiang, H., and Meka, R. Resolving matrix spencer conjecture up to poly-logarithmic rank.  In STOC’23—Proceedings of the 55th Annual ACM Symposium on Theory of Computing ([2023] ©2023), ACM, New York, pp. 1814–1819.
  * [12] Bansal, N., Jiang, H., Meka, R., Singla, S., and Sinha, M. Prefix discrepancy, smoothed analysis, and combinatorial vector balancing.  In 13th Innovations in Theoretical Computer Science Conference, vol. 215 of LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022, pp. Art. No. 13, 22.
  * [13] Bansal, N., Jiang, H., Meka, R., Singla, S., and Sinha, M. Smoothed analysis of the Komlós conjecture.  In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) (2022), Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
  * [14] Bansal, N., Laddha, A., and Vempala, S. A unified approach to discrepancy minimization.  In Approximation, randomization, and combinatorial optimization. Algorithms and techniques, vol. 245 of LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022, pp. Art. No. 1, 22.
  * [15] Bansal, N., and Meka, R. On the discrepancy of random low degree set systems.  Random Structures Algorithms 57, 3 (2020), 695–705.
  * [16] Batson, J., Spielman, D. A., and Srivastava, N. Twice-Ramanujan sparsifiers.  SIAM J. Comput. 41, 6 (2012), 1704–1721.
  * [17] Borst, S., Dadush, D., Huiberts, S., and Tiwari, S. On the integrality gap of binary integer programs with Gaussian data.  Math. Program. 197, 2, Ser. B (2023), 1221–1263.
  * [18] Borst, S., Dadush, D., and Mikulincer, D. Integrality gaps for random integer programs via discrepancy.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2023), SIAM, Philadelphia, PA, pp. 1692–1733.
  * [19] Chandrasekaran, K., and Vempala, S. S. Integer feasibility of random polytopes.  In ITCS’14—Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science (2014), ACM, New York, pp. 449–458.
  * [20] Chatterjee, S. Superconcentration and related topics, vol. 15.  Springer, 2014.
  * [21] Chazelle, B. The discrepancy method.  Cambridge University Press, Cambridge, 2000.  Randomness and complexity.
  * [22] Cook, W., Gerards, A. M. H., Schrijver, A., and Tardos, E. Sensitivity theorems in integer linear programming.  Math. Programming 34, 3 (1986), 251–264.
  * [23] Dadush, D., and Huiberts, S. A friendly smoothed analysis of the simplex method.  SIAM J. Comput. 49, 5 (2020), STOC18–449–STOC18–499.
  * [24] Dadush, D., Jiang, H., and Reis, V. A new framework for matrix discrepancy: partial coloring bounds via mirror descent.  In STOC ’22—Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing ([2022] ©2022), ACM, New York, pp. 649–658.
  * [25] Dadush, D., Nikolov, A., Talwar, K., and Tomczak-Jaegermann, N. Balancing vectors in any norm.  In 59th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2018. IEEE Computer Soc., Los Alamitos, CA, 2018, pp. 1–10.
  * [26] Dadush, D. N. Integer programming, lattice algorithms, and deterministic volume estimation.  Georgia Institute of Technology, 2012.
  * [27] Dyer, M. E., and Frieze, A. M. Probabilistic analysis of the multidimensional knapsack problem.  Mathematics of Operations Research 14, 1 (1989), 162–176.
  * [28] Ezra, E., and Lovett, S. On the Beck-Fiala conjecture for random set systems.  Random Structures Algorithms 54, 4 (2019), 665–675.
  * [29] Franks, C., and Saks, M. On the discrepancy of random matrices with many columns.  Random Structures Algorithms 57, 1 (2020), 64–96.
  * [30] Friedgut, E. Sharp thresholds of graph properties, and the $k$-sat problem.  J. Amer. Math. Soc. 12, 4 (1999), 1017–1054.  With an appendix by Jean Bourgain.
  * [31] Friedgut, E., and Kalai, G. Every monotone graph property has a sharp threshold.  Proceedings of the American mathematical Society 124, 10 (1996), 2993–3002.
  * [32] Gamarnik, D., Kızıldağ, E. C., Perkins, W., and Xu, C. Algorithms and barriers in the symmetric binary perceptron model.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) (2022), pp. 576–587.
  * [33] Hoberg, R., and Rothvoss, T. A Fourier-analytic approach for the discrepancy of random set systems.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (2019), SIAM, Philadelphia, PA, pp. 2547–2556.
  * [34] Hopkins, S. B., Raghavendra, P., and Shetty, A. Matrix discrepancy from quantum communication.  In STOC ’22—Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing ([2022] ©2022), ACM, New York, pp. 637–648.
  * [35] Kalai, G. Boolean functions: influence, threshold and noise.  In European Congress of Mathematics. Eur. Math. Soc., Zürich, 2018, pp. 85–110.
  * [36] Kizildag, E. C., and Wakhare, T. Symmetric perceptron with random labels.  In Fourteenth International Conference on Sampling Theory and Applications (2023).
  * [37] Kunisky, D., and Zhang, P. Online algorithms and lower bounds for average-case matrix discrepancy.  arXiv preprint arXiv:2307.10055 (2023).
  * [38] Kyng, R., Luh, K., and Song, Z. Four deviations suffice for rank 1 matrices.  Adv. Math. 375 (2020), 107366, 17.
  * [39] Matoušek, J. Geometric discrepancy, vol. 18 of Algorithms and Combinatorics.  Springer-Verlag, Berlin, 1999.  An illustrated guide.
  * [40] Milgrom, P., and Segal, I. Envelope theorems for arbitrary choice sets.  Econometrica 70, 2 (2002), 583–601.
  * [41] Minzer, D., Sah, A., and Sawhney, M. On perfectly friendly bisections of random graphs.  arXiv preprint arXiv:2305.03543 (2023).
  * [42] Nakajima, S., and Sun, N. Sharp threshold sequence and universality for Ising perceptron models.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2023), SIAM, Philadelphia, PA, pp. 638–674.
  * [43] Perkins, W., and Xu, C. Frozen 1-RSB structure of the symmetric Ising perceptron.  In STOC ’21—Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing ([2021] ©2021), ACM, New York, pp. 1579–1588.
  * [44] Potukuchi, A. Discrepancy in random hypergraph models.  arXiv preprint arXiv:1811.01491 (2018).
  * [45] Reis, V., and Rothvoss, T. Linear size sparsifier and the geometry of the operator norm ball.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (2020), SIAM, Philadelphia, PA, pp. 2337–2348.
  * [46] Roughgarden, T. Beyond worst-case analysis.  Communications of the ACM 62, 3 (2019), 88–96.
  * [47] Sah, A., and Sawhney, M. Distribution of the threshold for the symmetric perceptron.  In (To appear) 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) (2023).
  * [48] Shcherbina, M., and Tirozzi, B. Rigorous solution of the Gardner problem.  Comm. Math. Phys. 234, 3 (2003), 383–422.
  * [49] Spencer, J. Ten lectures on the probabilistic method, second ed., vol. 64 of CBMS-NSF Regional Conference Series in Applied Mathematics.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994.
  * [50] Spielman, D. A., and Teng, S.-H. Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time.  J. ACM 51, 3 (2004), 385–463.
  * [51] Steele, J. M. The Cauchy-Schwarz master class.  AMS/MAA Problem Books Series. Mathematical Association of America, Washington, DC; Cambridge University Press, Cambridge, 2004.  An introduction to the art of mathematical inequalities.
  * [52] Talagrand, M. Self-averaging and the space of interactions in neural networks.  Random Structures Algorithms 14, 3 (1999), 199–213.
  * [53] Talagrand, M. Mean field models for spin glasses. Volume I.  Springer-Verlag, Berlin, 2011.
  * [54] Talagrand, M. Mean field models for spin glasses. Volume II.  Springer, Heidelberg, 2011.
  * [55] Turner, P., Meka, R., and Rigollet, P. Balancing Gaussian vectors in high dimension.  In Conference on Learning Theory (2020), pp. 3455–3486.
  * [56] Xu, C. Sharp threshold for the Ising perceptron model.  Ann. Probab. 49, 5 (2021), 2399–2415.