# Rapid Multi-band Space-Based Optical Timing: Revolutionizing Accretion
Physics

Krista Lynne Smith 1,∗

###### Abstract

Optical timing with rapid, seconds-to-minutes cadences with high photometric
precision and gap-free long baselines is necessary for an unambiguous physical
picture of accretion phenomena, and is only possible from space. Exoplanet-
hunting missions like Kepler and TESS have offered an outstanding new window
into detailed jet and accretion physics, but have been severely hampered by
incomplete calibration and systematics treatments and, most especially, a
monochromatic single wide bandpass. Advances made using Kepler and TESS survey
data, when considered alongside detailed, expensive multi-color experiments
done from the ground, reveal the enormous potential of a space-based multi-
color optical timing mission with a high energy focus.

##  1 Keywords:

AGN - Active Galactic Nucleus, Blazars, time domain, accretion, black holes

##  2 Introduction

During its prime mission from 2009 - 2013, the _Kepler_ spacecraft fulfilled
its brief spectacularly, discovering thousands of extrasolar planets. Its
success was due to three major properties of the mission tailored to the
search for exoplanet transits: rapid, 30-minute cadence of the observations, a
long and uninterrupted $\sim 4$ year baseline, and unprecedented photometric
precision. The lack of seasonal and diurnal gaps, so often the bane of ground-
based monitoring campaigns, enabled a full temporal sampling space. The
properties that made the mission such an exemplary planet-finder also raised
the potential for it to study variable high-energy phenomena in unexplored
parameter spaces as well. A number of investigations into active galactic
nuclei (AGN) and other accreting systems took place, but were hampered
significantly by instrumental systematics that required complex bespoke
reduction techniques often difficult to reproduce. To a large extent, this was
due to the non-exoplanet applications requiring more complete calibration than
needed for detecting the strictly periodic point-source variation that
characterizes exoplanet transits; see Smith (2019) for a complete discussion,
and Howell (2020) for a summary of _Kepler_ results, including those beyond
exoplanets.

The successor to _Kepler_ , the Transiting Exoplanet Survey Satellite (TESS)
was launched in 2018 with the same high precision, rapid cadence, and
monolithic bandpass (with a redder central wavelength) as its predecessor, but
with a few key differences, including the release of early-stage full frame
images (FFIs) for the entire survey region and a much larger, nearly all-sky
survey footprint, with the tradeoff of shorter baselines (27 days to 1 year,
depending on ecliptic latitude). From the start, TESS made itself more
amenable to non-exoplanet science applications by releasing flexible support
software for reduction (e.g. Lightkurve Collaboration et al., 2018, originally
designed for K2 data) and calibration products for the FFIs. Nonetheless, TESS
systematics make time domain analysis of stochastically varying sources like
AGN quite challenging, especially when stitching light curves across many
27-day sectors. Fortunately, TESS supported user-created reduction software as
part of its guest observer program, resulting in a proliferation of pipelines
for both generic and highly customized science applications. Still, many works
publish light curves that are badly affected by systematics.

In addition to challenging systematics due to electronics and background
light, both missions also have a single white-light bandpass. While an
efficient choice for transient and exoplanet searches, this prohibits the vast
amount of astrophysics present in cross-band correlations at rapid timescales.
Because these investigations require significant resources with existing
instruments, almost all experiments at high cadence are done in expensive
single object case studies.

##  3 Potential High-Energy Applications of Multi-colored Space-based Timing

###  3.1 Searching for Binary Supermassive Black Holes

A confident census of the separations, mass ratios, and spins of binary
supermassive black holes is an important prior for the multimessenger
detections of binary inspirals through gravitational waves, both the
stochastic background of orbiting binary pairs as seen by pulsar timing arrays
like NANOGrav (Agazie et al., 2023) and in future signals expected from the
upcoming LISA observatory (Amaro-Seoane et al., 2017). One potential signal is
periodicity in AGN light curves due to Doppler boosting of an orbiting pair,
periodic accretion episodes in the mini-disks, or precessing jets (e.g.,
D’Orazio et al., 2015; Ryan and MacFadyen, 2017; Charisi et al., 2018; Combi
et al., 2022); observed candidates of each of these have been put forth in
varying numbers (e.g., Graham et al., 2015; Liu et al., 2016; Britzen et al.,
2018; Liao et al., 2021). However, the red noise nature of accretion disk and
jet variability can lead to false positives in searches for binaries, which
are seriously exacerbated by gaps in light curves. As the following examples
demonstrate, far less ambiguous signatures of binary AGN are possible with
high-cadence, uninterrupted monitoring, and adding color information increases
the confidence even more.

Self-lensing flares, wherein a foreground massive black hole gravitationally
lenses the emission from the mini-disk around the background hole in an
orbiting pair, is a periodic signal that occurs at a predictable phase of a
doppler-boosted periodic oscillation, and is not degenerate with other
physical explanations (D’Orazio and Di Stefano, 2018). Only one such candidate
exists currently, and it is from Kepler data, which was capable of capturing
the approximately week-long flare event with very high significance (Hu et
al., 2020).

As shown by D’Orazio and Di Stefano (2018), when the background accretion disk
is near enough to be lensed as a source of finite size, multi-band light
curves would provide a very sensitive probe of the structure of that accretion
flow, a totally unique observable of the fueling of binaries. If the
background disk is a point source, lensing is, as usual, achromatic; this
would make the self-lensing flare completely distinct from other AGN flares.

The technique of “varstrometry” has recently been used with _Gaia_ data to
locate binary AGN candidates (at much larger separations than the self-lensing
or periodicity techniques) using astrometric noise: two AGN will vary
independently, so even when they are convolved in a low-resolution image, the
image’s centroid will shift as one or the other AGN becomes brighter (Liu,
2015; Shen et al., 2019; Hwang et al., 2020). This method has successfully
recovered a large number of known close binaries, and led to the discovery of
many new binaries (e.g., Chen et al., 2022), although the technique is also
useful for discovering lensed images of single quasars (e.g., Shen et al.,
2021; Springer and Ofek, 2021). Rapid monitoring will allow for tighter
constraints on astrometric noise, as well as noise at different variability
timescales, and reveal a wider population of astrometrically-varying binary
candidates. Furthermore, adding colors to the “varstrometry” method widens the
discovery space even further; as the centroid shifts, so will the peak
wavelength at which the convolved source is varying. This will lead to
distinct centroids in different wavebands, as shown by Liu (2015) and Liu
(2016). The achromaticity of gravitational lensing also suggests that multi-
color varstrometry is likely to be able to differentiate between binary AGN
pairs and lensing as the underlying cause of the shifting light center.

###  3.2 Relativistic Jet Physics in Blazars

Blazars vary significantly at a huge variety of timescales, from a few minutes
to a few years, in every waveband in which they have been studied. A vast
literature exists focused on simultaneous monitoring of blazars across the
full electormagnetic spectrum, with the most frequent goal being the
determination of the origin of the two peaks of the blazar spectral energy
distribution (SED). The lower-energy peak can span the radio to UV (so-called
“low-synchrotron peak” or LSP blazars) or X-ray (“high-synchrotron peak”; HSP)
wavebands, while the higher energy peak extends blue-ward from a trough after
the low energy peak, including the gamma ray spectral region. The physical
origin of the low-energy peak is well understood as synchrotron emission from
electrons in the relativistic jet powered by the supermassive black hole. The
gamma ray emission in the high-energy peak could come from leptonic processes
like Compton-upscattered thermal photons from the accretion disk or obscuring
torus (external Compton models; Sikora et al., 1993) or upscattered
synchrotron photons from the jet itself (self-Compton models; Mastichiadis and
Kirk, 1997). Alternatively, the gamma ray emission could come from hadronic
processes such as pion decay or proton- synchrotron radiation (e.g., Böttcher
et al., 2009; Reimer, 2012). Self-compton models imply that a strong
correlation between variations in the lower and higher energy peaks would be
expected, while hadronic models might suggest a weak or no correlation.

Within the optical band, multi-color monitoring has been used in a large
number of ground-based surveys with semi-daily to weekly sampling over many
years to study the physics of blazar flares. Bonning et al. (2012) showed
convincing evidence for a shift in the low energy peak of the blazar 3C 454.3
over a 24 hour flaring period in 2009 using multi-band optical-IR SMARTS
monitoring, and reported a redder-when-brighter trend in flat-spectrum radio
quasars (FSRQs). Recent ground-based studies have found a bluer-when-brighter
trend in many blazars, as well as using the rapid minutes-scale variability to
determine upper limits on black hole masses, a very challenging quantity to
measure in beamed targets like these (Chang et al., 2023; Li et al., 2024).
Other studies have found that whether a source becomes bluer or redder when
brightening depends on its optical spectral classification as an FSRQ or a BL
Lac object (Zhang et al., 2023). The amount and color lag properties of so-
called “microvariability” on minutes-to-hours timescales can be used to study
the uniformity of particle flow within the jets and meaningfully constrain the
amount of turbulence present (Marscher, 2014; Roy et al., 2023). The degree to
which the color index changes on rapid timescales can also determine whether a
rapidly-varying jet angle due to precession or a wobbling jet (and therefore a
changing bulk Doppler factor) is contributing to the observed variability
(Marchesini et al., 2016; Agarwal et al., 2016). These discoveries, however,
have taken place in detailed, observationally expensive monitoring campaigns
of single objects, requiring global networks of ground-based telescopes to
avoid diurnal and weather-dependent gaps. Space-based timing, especially from
TESS, has enabled discoveries of rapid quasi-periodicities in the optical jet
emission has led to speculation about the nature of fluid instabilities in the
jet boundaries, such as the kink instability (Jorstad et al., 2022; Tripathi
et al., 2024a, b). However, as the TESS spacecraft has only a single wide
bandpass, no color index information is present, preventing the use of these
data for studying rapid inter-band lags in large samples.

###  3.3 Detailed Physics of Accretion Flows

Accretion disks around supermassive black holes radiate primarily in the UV
and optical, and are conceived as a series of annuli radiating like local
blackbodies, decreasing in temperature with distance from the hole. This has
led to enormous efforts to map accretion disks and track variations moving
through accretion disks with simultaneous, multi-color modeling, to great
effect. Edelson et al. (2015) and the STORM team conducted a monumental effort
to monitor the Seyfert galaxy NGC 5548 with Swift and daily with HST in the
X-ray, UV, and a range of optical wavebands. The results are spectacular,
showing a clear signal of UV-optical lags agreeing with this general thermal
annuli accretion disk theory, but with surprising results for the size of the
accretion disk and with possible implications for the geometry of the broad-
line region. Further studies of individual objects with multiband, daily
monitoring by STORM have led to even further insights, including detailed maps
of accretion disk temperature fluctuations with both temporal and spatial
resolution (De Rosa et al., 2015; Cackett et al., 2023; Neustadt et al.,
2024).

The unique insights offered by these studies cannot be overstated: this is the
only direct observable into the behavior of matter in the extreme environments
of AGN disks, except for direct imaging of accretion flows by, for example,
the Event Horizon Telescope (EHT Collaboration et al., 2019; Collaboration,
2023), or deep _Chandra_ imaging of gas near the Bondi radius (Baganoff et
al., 2003; Wong et al., 2011; Russell et al., 2015; Bambic et al., 2023),
which is only possible for a handful of nearby objects.

With cadence on minutes timescales like those afforded by TESS, but in the
multiple colors explored with STORM, such insights would extend to the
smallest regions of the optical disk, reaching into the most extreme space-
time environments of the accreting matter. Ray tracing simulations indicate
that at these scales, different wavelengths may trace the space-time
environment itself (e.g., Bromley et al., 1997).

When combined with simultaneous X-ray monitoring, multi-band timing
experiments provide unique information about the geometry and location of the
X-ray corona, a major contested question in AGN physics. A wealth of longer-
baseline, lower-cadence X-ray / UV / optical campaigns have provided
conflicting results in the question of the origin of variations: do flares
initiate in the corona, which is located above the disk like a “lamp-post”,
and get reprocessed successively by the accretion disk at different radii, or
do flares initaite in the disk through magnetic reconnection or bulk accretion
flow variations, and propagate inward to the corona? (For a recent review, see
Cackett et al., 2021). The advent of very rapid X-ray timing with experiments
like NICER (Gendreau et al., 2012), which has joint programs with TESS
already, offers the possibility of simultaneous, rapid multi-band optical and
X-ray experiments that probe this relationship at the smallest relevant
physical scales.

###  3.4 Other Applications

In addition to the science cases discussed in detail here, there are numerous
other applications to AGN and accretion physics. Variability has been
identified as an important means of identifying potential dwarf AGN; that is,
actively accreting intermediate mass black holes (IMBHs) (Baldassare et al.,
2020), and indeed many low-mass AGN have been noted in TESS light curves
(Burke et al., 2020; Treiber et al., 2023). Rapid, highly photometrically
accurate space-based timing is well-equipped to build a census of these
objects orthogonal to those found in expensive radio and X-ray imaging
searches. This is important, because the occupation fraction of AGN in dwarf
galaxies has major implications for the nature of black hole seeds in the
early universe (see Greene et al., 2020, for a review).

Transients also offer a tantalizing peek into accretion physics, especially
those associated with tidal disruption events (TDEs) in which a massive black
hole consumes a stellar object, producing a temporary accretion flow and
resulting in a large, multi-wavlength flare (Evans and Kochanek, 1989; Gezari,
2021). TESS has seen a number of such events (e.g., Holoien et al., 2019), and
has detected other interesting fast nuclear transients (including some
repeating anomalous signals) in galaxies (e.g., Payne et al., 2023). Color
information provides much more physical interpretability than monochrome
transient detection, including characterization of the transient’s evolution
and information that helps constrain the nature of the disrupted star.

##  4 Conclusion: The Impact of a Rapid, Multicolor Space-Based High-Energy
Satellite

Despite their original design goal of finding and determining the orbital
parameters of exoplanets, the _Kepler_ and TESS missions’ rapid optical timing
with high photometric precision and uninterrupted space-based monitoring were
powerful tools for exploring the high energy astrophysics of accretion and
jets. Observers in these areas overcame major data reduction challenges in
order to use these instruments, driven mainly by the missions’ original design
goals (see Smith, 2019, for a detailed description of challenges). Among the
biggest obstacles to achieving complete pictures of the phenomena under
investigation are the monolothic one-color bandpasses of the experiments and
the daunting uncalibrated systematics that mimic stochastic astrophysical
signals; others include the large pixel size (contributing to crowding, a
major issue for faint sources) and a bright limiting magnitude that severely
hampers extragalactic sample sizes.

It is my perspective that a survey mission with many of the properties of
_Kepler_ and TESS, but with high-energy applications in mind, would provide
major leaps forward in all of the science applications listed here. A mission
with $\sim 10-30$ minute cadence, multiple optical colors, and a deeper
limiting magnitude, even at the expense of sky coverage (for example, limited
to small, well-studied extragalactic fields) and with careful calibration
geared towards recovering stochastic signal is a natural next step towards
space-based high energy astrophysics in the optical regime, following an
existing budget-friendly template, that would offer outstanding science
returns. All extragalactic applications would benefit substantially from
deeper limiting magnitudes than those probed by the exoplanet missions, due to
enormous increases in sample size at magnitudes $>20$ even with reduced sky
coverage. Rapid cadence offers an unprecedented window into jet and accretion
disk phenomenology only accessible before with intensive global ground-based
campaigns. Color information opens up a wide range of phenomenologies through
the study of interband lags and leads, while also breaking degeneracies in
searches for close binary AGN pairs, the source population for low-frequency
gravitational waves. I urge the rest of the time domain community to consider
what such a mission could do for their respective fields!

## Author Contributions

KLS is the sole author, and is responsible for all the opinions in this
article, and has solely compiled the examples and references therein.

## References

  * Agarwal et al. (2016) Agarwal, A., Gupta, A. C., Bachev, R., Strigachev, A., Semkov, E., Wiita, P. J., et al. (2016).  Multiband optical variability of the blazar S5 0716+714 in outburst state during 2014-2015.  _MNRAS_ 455, 680–690.  10.1093/mnras/stv2345
  * Agazie et al. (2023) Agazie, G., Anumarlapudi, A., Archibald, A. M., Arzoumanian, Z., Baker, P. T., Bécsy, B., et al. (2023).  The NANOGrav 15 yr Data Set: Evidence for a Gravitational-wave Background.  _ApJ_ 951, L8.  10.3847/2041-8213/acdac6
  * Amaro-Seoane et al. (2017) Amaro-Seoane, P., Audley, H., Babak, S., Baker, J., Barausse, E., Bender, P., et al. (2017).  Laser Interferometer Space Antenna.  _arXiv e-prints_ , arXiv:1702.0078610.48550/arXiv.1702.00786
  * Baganoff et al. (2003) Baganoff, F. K., Maeda, Y., Morris, M., Bautz, M. W., Brandt, W. N., Cui, W., et al. (2003).  Chandra X-Ray Spectroscopic Imaging of Sagittarius A* and the Central Parsec of the Galaxy.  _ApJ_ 591, 891–915.  10.1086/375145
  * Baldassare et al. (2020) Baldassare, V. F., Geha, M., and Greene, J. (2020).  A Search for Optical AGN Variability in 35,000 Low-mass Galaxies with the Palomar Transient Factory.  _ApJ_ 896, 10.  10.3847/1538-4357/ab8936
  * Bambic et al. (2023) Bambic, C. J., Russell, H. R., Reynolds, C. S., Fabian, A. C., McNamara, B. R., and Nulsen, P. E. J. (2023).  AGN feeding and feedback in M84: from kiloparsec scales to the Bondi radius.  _MNRAS_ 522, 4374–4391.  10.1093/mnras/stad824
  * Bonning et al. (2012) Bonning, E., Urry, C. M., Bailyn, C., Buxton, M., Chatterjee, R., Coppi, P., et al. (2012).  SMARTS Optical and Infrared Monitoring of 12 Gamma-Ray Bright Blazars.  _ApJ_ 756, 13.  10.1088/0004-637X/756/1/13
  * Böttcher et al. (2009) Böttcher, M., Reimer, A., and Marscher, A. P. (2009).  Implications of the very High Energy Gamma-Ray Detection of the Quasar 3C279.  _ApJ_ 703, 1168–1175.  10.1088/0004-637X/703/1/1168
  * Britzen et al. (2018) Britzen, S., Fendt, C., Witzel, G., Qian, S. J., Pashchenko, I. N., Kurtanidze, O., et al. (2018).  OJ287: deciphering the ‘Rosetta stone of blazars.  _MNRAS_ 478, 3199–3219.  10.1093/mnras/sty1026
  * Bromley et al. (1997) Bromley, B. C., Chen, K., and Miller, W. A. (1997).  Line Emission from an Accretion Disk around a Rotating Black Hole: Toward a Measurement of Frame Dragging.  _ApJ_ 475, 57–64.  10.1086/303505
  * Burke et al. (2020) Burke, C. J., Shen, Y., Chen, Y.-C., Scaringi, S., Faucher-Giguere, C.-A., Liu, X., et al. (2020).  Optical Variability of the Dwarf AGN NGC 4395 from the Transiting Exoplanet Survey Satellite.  _ApJ_ 899, 136.  10.3847/1538-4357/aba3ce
  * Cackett et al. (2021) Cackett, E. M., Bentz, M. C., and Kara, E. (2021).  Reverberation mapping of active galactic nuclei: from X-ray corona to dusty torus.  _iScience_ 24, 102557.  10.1016/j.isci.2021.102557
  * Cackett et al. (2023) Cackett, E. M., Gelbord, J., Barth, A. J., De Rosa, G., Edelson, R., Goad, M. R., et al. (2023).  AGN STORM 2. IV. Swift X-Ray and Ultraviolet/Optical Monitoring of Mrk 817.  _ApJ_ 958, 195.  10.3847/1538-4357/acfdac
  * Chang et al. (2023) Chang, X., Yi, T. F., Xiong, D. R., Liu, C. X., Yang, X., Li, H. Z., et al. (2023).  Multicolour optical variability monitoring of blazars with high time resolution.  _MNRAS_ 520, 4118–4133.  10.1093/mnras/stad409
  * Charisi et al. (2018) Charisi, M., Haiman, Z., Schiminovich, D., and D’Orazio, D. J. (2018).  Testing the relativistic Doppler boost hypothesis for supermassive black hole binary candidates.  _MNRAS_ 476, 4617–4628.  10.1093/mnras/sty516
  * Chen et al. (2022) Chen, Y.-C., Hwang, H.-C., Shen, Y., Liu, X., Zakamska, N. L., Yang, Q., et al. (2022).  Varstrometry for Off-nucleus and Dual Subkiloparsec AGN (VODKA): Hubble Space Telescope Discovers Double Quasars.  _ApJ_ 925, 162.  10.3847/1538-4357/ac401b
  * Collaboration (2023) Collaboration, E. (2023).  First Sagittarius A* Event Horizon Telescope Results. I. The Shadow of the Supermassive Black Hole in the Center of the Milky Way.  _arXiv e-prints_ , arXiv:2311.0868010.48550/arXiv.2311.08680
  * Combi et al. (2022) Combi, L., Lopez Armengol, F. G., Campanelli, M., Noble, S. C., Avara, M., Krolik, J. H., et al. (2022).  Minidisk accretion onto spinning black hole binaries: Quasi-periodicities and outflows.  _The Astrophysical Journal_ 928, 187.  10.3847/1538-4357/ac532a
  * De Rosa et al. (2015) De Rosa, G., Peterson, B. M., Ely, J., Kriss, G. A., Crenshaw, D. M., Horne, K., et al. (2015).  Space Telescope and Optical Reverberation Mapping Project.I. Ultraviolet Observations of the Seyfert 1 Galaxy NGC 5548 with the Cosmic Origins Spectrograph on Hubble Space Telescope.  _ApJ_ 806, 128.  10.1088/0004-637X/806/1/128
  * D’Orazio and Di Stefano (2018) D’Orazio, D. J. and Di Stefano, R. (2018).  Periodic self-lensing from accreting massive black hole binaries.  _MNRAS_ 474, 2975–2986.  10.1093/mnras/stx2936
  * D’Orazio et al. (2015) D’Orazio, D. J., Haiman, Z., and Schiminovich, D. (2015).  Relativistic boost as the cause of periodicity in a massive black-hole binary candidate.  _Nature_ 525, 351–353.  10.1038/nature15262
  * Edelson et al. (2015) Edelson, R., Gelbord, J. M., Horne, K., McHardy, I. M., Peterson, B. M., Arévalo, P., et al. (2015).  Space Telescope and Optical Reverberation Mapping Project. II. Swift and HST Reverberation Mapping of the Accretion Disk of NGC 5548.  _ApJ_ 806, 129.  10.1088/0004-637X/806/1/129
  * EHT Collaboration et al. (2019) EHT Collaboration, Akiyama, K., Alberdi, A., Alef, W., Asada, K., Azulay, R., et al. (2019).  First M87 Event Horizon Telescope Results. IV. Imaging the Central Supermassive Black Hole.  _ApJ_ 875, L4.  10.3847/2041-8213/ab0e85
  * Evans and Kochanek (1989) Evans, C. R. and Kochanek, C. S. (1989).  The Tidal Disruption of a Star by a Massive Black Hole.  _ApJ_ 346, L13.  10.1086/185567
  * Gendreau et al. (2012) Gendreau, K. C., Arzoumanian, Z., and Okajima, T. (2012).  The Neutron star Interior Composition ExploreR (NICER): an Explorer mission of opportunity for soft x-ray timing spectroscopy.  In _Space Telescopes and Instrumentation 2012: Ultraviolet to Gamma Ray_ , eds. T. Takahashi, S. S. Murray, and J.-W. A. den Herder. vol. 8443 of _Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series_ , 844313.  10.1117/12.926396
  * Gezari (2021) Gezari, S. (2021).  Tidal Disruption Events.  _ARA &A_ 59, 21–58.  10.1146/annurev-astro-111720-030029
  * Graham et al. (2015) Graham, M. J., Djorgovski, S. G., Stern, D., Drake, A. J., Mahabal, A. A., Donalek, C., et al. (2015).  A systematic search for close supermassive black hole binaries in the Catalina Real-time Transient Survey.  _MNRAS_ 453, 1562–1576.  10.1093/mnras/stv1726
  * Greene et al. (2020) Greene, J. E., Strader, J., and Ho, L. C. (2020).  Intermediate-mass black holes.  _Annual Review of Astronomy and Astrophysics_ 58, 257–312.  10.1146/annurev-astro-032620-021835
  * Holoien et al. (2019) Holoien, T. W.-S., Vallely, P. J., Auchettl, K., Stanek, K. Z., Kochanek, C. S., French, K. D., et al. (2019).  Discovery and early evolution of asassn-19bt, the first tde detected by tess.  _The Astrophysical Journal_ 883, 111.  10.3847/1538-4357/ab3c66
  * Howell (2020) Howell, S. B. (2020).  _The NASA Kepler Mission_
  * Hu et al. (2020) Hu, B. X., D’Orazio, D. J., Haiman, Z., Smith, K. L., Snios, B., Charisi, M., et al. (2020).  Spikey: self-lensing flares from eccentric SMBH binaries.  _MNRAS_ 495, 4061–4070.  10.1093/mnras/staa1312
  * Hwang et al. (2020) Hwang, H.-C., Shen, Y., Zakamska, N., and Liu, X. (2020).  Varstrometry for Off-nucleus and Dual Subkiloparsec AGN (VODKA): Methodology and Initial Results with Gaia DR2.  _ApJ_ 888, 73.  10.3847/1538-4357/ab5c1a
  * Jorstad et al. (2022) Jorstad, S. G., Marscher, A. P., Raiteri, C. M., Villata, M., Weaver, Z. R., Zhang, H., et al. (2022).  Rapid quasi-periodic oscillations in the relativistic jet of BL Lacertae.  _Nature_ 609, 265–268.  10.1038/s41586-022-05038-9
  * Li et al. (2024) Li, H.-Z., Guo, D.-F., Qin, L.-H., Yi, T.-F., Liu, F., Gao, Q.-G., et al. (2024).  The optical intra-day variability of BL laceratae object 2200 + 420.  _MNRAS_ 528, 6823–6835.  10.1093/mnras/stae422
  * Liao et al. (2021) Liao, W.-T., Chen, Y.-C., Liu, X., Holgado, A. M., Guo, H., Gruendl, R., et al. (2021).  Discovery of a candidate binary supermassive black hole in a periodic quasar from circumbinary accretion variability.  _MNRAS_ 500, 4025–4041.  10.1093/mnras/staa3055
  * Lightkurve Collaboration et al. (2018) [Dataset] Lightkurve Collaboration, Cardoso, J. V. d. M., Hedges, C., Gully-Santiago, M., Saunders, N., Cody, A. M., et al. (2018).  Lightkurve: Kepler and TESS time series analysis in Python.  Astrophysics Source Code Library, record ascl:1812.013
  * Liu et al. (2016) Liu, T., Gezari, S., Burgett, W., Chambers, K., Draper, P., Hodapp, K., et al. (2016).  A Systematic Search for Periodically Varying Quasars in Pan-STARRS1: An Extended Baseline Test in Medium Deep Survey Field MD09.  _ApJ_ 833, 6.  10.3847/0004-637X/833/1/6
  * Liu (2015) Liu, Y. (2015).  Finding binary active galactic nuclei by the centroid shift in imaging surveys.  _A &A_ 580, A133.  10.1051/0004-6361/201526266
  * Liu (2016) Liu, Y. (2016).  Finding binary active galactic nuclei candidates by the centroid shift in imaging surveys. II. Testing the method with SDSS J233635.75-010733.7.  _A &A_ 592, L4.  10.1051/0004-6361/201628430
  * Marchesini et al. (2016) Marchesini, E. J., Andruchow, I., Cellone, S. A., Combi, J. A., Zibecchi, L., Martí, J., et al. (2016).  Optical flux behaviour of a sample of Fermi blazars.  _A &A_ 591, A21.  10.1051/0004-6361/201527632
  * Marscher (2014) Marscher, A. P. (2014).  Turbulent, Extreme Multi-zone Model for Simulating Flux and Polarization Variability in Blazars.  _ApJ_ 780, 87.  10.1088/0004-637X/780/1/87
  * Mastichiadis and Kirk (1997) Mastichiadis, A. and Kirk, J. G. (1997).  Variability in the synchrotron self-Compton model of blazar emission.  _A &A_ 320, 19–25.  10.48550/arXiv.astro-ph/9610058
  * Neustadt et al. (2024) Neustadt, J. M. M., Kochanek, C. S., Montano, J., Gelbord, J., Barth, A. J., De Rosa, G., et al. (2024).  AGN STORM 2. VI. Mapping Temperature Fluctuations in the Accretion Disk of Mrk 817.  _ApJ_ 961, 219.  10.3847/1538-4357/ad1386
  * Payne et al. (2023) Payne, A. V., Auchettl, K., Shappee, B. J., Kochanek, C. S., Boyd, P. T., Holoien, T. W. S., et al. (2023).  Chandra, HST/STIS, NICER, Swift, and TESS Detail the Flare Evolution of the Repeating Nuclear Transient ASASSN -14ko.  _ApJ_ 951, 134.  10.3847/1538-4357/acd455
  * Reimer (2012) Reimer, A. (2012).  On the Physics of Hadronic Blazar Emission Models.  In _Journal of Physics Conference Series_. vol. 355 of _Journal of Physics Conference Series_ , 012011.  10.1088/1742-6596/355/1/012011
  * Roy et al. (2023) Roy, A., Gupta, A. C., Chitnis, V. R., Cellone, S. A., Raiteri, C. M., Romero, G. E., et al. (2023).  Study of Variability in Long-term Multiwavelength Optical Lightcurves of Blazar AO 0235+164.  _ApJS_ 265, 14.  10.3847/1538-4365/acb059
  * Russell et al. (2015) Russell, H. R., Fabian, A. C., McNamara, B. R., and Broderick, A. E. (2015).  Inside the Bondi radius of M87.  _MNRAS_ 451, 588–600.  10.1093/mnras/stv954
  * Ryan and MacFadyen (2017) Ryan, G. and MacFadyen, A. (2017).  Minidisks in binary black hole accretion.  _The Astrophysical Journal_ 835, 199.  10.3847/1538-4357/835/2/199
  * Shen et al. (2021) Shen, Y., Chen, Y.-C., Hwang, H.-C., Liu, X., Zakamska, N., Oguri, M., et al. (2021).  A hidden population of high-redshift double quasars unveiled by astrometry.  _Nature Astronomy_ 5, 569–574.  10.1038/s41550-021-01323-1
  * Shen et al. (2019) Shen, Y., Hwang, H.-C., Zakamska, N., and Liu, X. (2019).  Varstrometry for Off-nucleus and Dual Sub-Kpc AGN (VODKA): How Well Centered Are Low-z AGN?  _ApJ_ 885, L4.  10.3847/2041-8213/ab4b54
  * Sikora et al. (1993) Sikora, M., Begelman, M. C., and Rees, M. J. (1993).  Comptonization of external radiation in blazars.  In _Compton Gamma-ray Observatory_ , eds. M. Friedlander, N. Gehrels, and D. J. Macomb. vol. 280 of _American Institute of Physics Conference Series_ , 598–602.  10.1063/1.44292
  * Smith (2019) Smith, K. L. (2019).  The vast potential of exoplanet satellites for high-energy astrophysics.  _Astronomische Nachrichten_ 340, 308–313.  10.1002/asna.201913615
  * Springer and Ofek (2021) Springer, O. M. and Ofek, E. O. (2021).  Measuring time delays - II. Using observations of the unresolved flux and astrometry.  _MNRAS_ 508, 3166–3180.  10.1093/mnras/stab2432
  * Treiber et al. (2023) Treiber, H. P., Hinkle, J. T., Fausnaugh, M. M., Shappee, B. J., Kochanek, C. S., Vallely, P. J., et al. (2023).  Revealing AGNs through TESS variability.  _MNRAS_ 525, 5795–5812.  10.1093/mnras/stad2530
  * Tripathi et al. (2024a) Tripathi, A., Smith, K. L., Wiita, P. J., and Wagoner, R. V. (2024a).  Optical quasi-periodic oscillations in the TESS light curves of three blazars.  _MNRAS_ 527, 9132–9144.  10.1093/mnras/stad3744
  * Tripathi et al. (2024b) Tripathi, A., Smith, K. L., Wiita, P. J., and Wagoner, R. V. (2024b).  Search for quasi-periodic oscillations in TESS light curves of bright Fermi Blazars.  _MNRAS_ 528, 6608–6618.  10.1093/mnras/stae410
  * Wong et al. (2011) Wong, K.-W., Irwin, J. A., Yukita, M., Million, E. T., Mathews, W. G., and Bregman, J. N. (2011).  Resolving the Bondi Accretion Flow toward the Supermassive Black Hole of NGC 3115 with Chandra.  _ApJ_ 736, L23.  10.1088/2041-8205/736/1/L23
  * Zhang et al. (2023) Zhang, B.-K., Tang, W.-F., Wang, C.-X., Wu, Q., Jin, M., Dai, B.-Z., et al. (2023).  The optical spectral features of 27 Fermi blazars.  _MNRAS_ 519, 5263–5270.  10.1093/mnras/stac3795


# The sample complexity of ERMs
in stochastic convex optimization

Daniel Carmon  Department of Mathematics, Technion-IIT
<EMAIL_ADDRESS>,  Roi Livni  Department of Electrical Engineering,
Tel Aviv University<EMAIL_ADDRESS>and  Amir Yehudayoff  Department
of Computer Science, University of Copenhagen and Department of Mathematics,
Technion-IIT<EMAIL_ADDRESS>
###### Abstract.

Stochastic convex optimization is one of the most well-studied models for
learning in modern machine learning. Nevertheless, a central fundamental
question in this setup remained unresolved:

> how many data points must be observed so that any empirical risk minimizer
> (ERM) shows good performance on the true population?

This question was proposed by Feldman who proved that
$\Omega(\frac{d}{\epsilon}+\frac{1}{\epsilon^{2}})$ data points are necessary
(where $d$ is the dimension and $\varepsilon>0$ is the accuracy parameter).
Proving an $\omega(\frac{d}{\epsilon}+\frac{1}{\epsilon^{2}})$ lower bound was
left as an open problem. In this work we show that in fact
$\tilde{O}(\frac{d}{\epsilon}+\frac{1}{\epsilon^{2}})$ data points are also
sufficient. This settles the question and yields a new separation between ERMs
and uniform convergence.

This sample complexity holds for the classical setup of learning bounded
convex Lipschitz functions over the Euclidean unit ball. We further generalize
the result and show that a similar upper bound holds for all symmetric convex
bodies. The general bound is composed of two terms: (i) a term of the form
$\tilde{O}(\frac{d}{\epsilon})$ with an inverse-linear dependence on the
accuracy parameter, and (ii) a term that depends on the statistical complexity
of the class of _linear_ functions (captured by the Rademacher complexity).
The proof builds a mechanism for controlling the behavior of stochastic convex
optimization problems.

R.L. is a recipient of a Google research scholar award and would like to
acknowledge his thanks. The research was supported, in part, by an ISF Grant
(2188 $\backslash$ 20), as well as supported by the ERC grant (GENERALIZATION,
10139692).

A.Y. is part of Basic Algorithms Research Copenhagen supported by the VILLUM
Foundation grant 16582, and also thanks the Pioneer Centre for AI, DNRF grant
number P1.

##  1\. Introduction

Stochastic convex optimization (SCO) is a benchmark framework that is widely
used for studying stochastic optimization algorithms such as gradient descent
and its variants. This is often justified by the simplicity of the framework
and the possibility of a rigorous analysis that can hint at the pros and cons
of various optimization techniques in practical setups such as machine
learning. It has also been studied in the optimization literature under the
name sample average approximation (SAA); see for example (15, 10) and
references within.

Stochastic convex optimization is particularly useful for understanding the
interaction between optimization and generalization in complex scenarios. The
works of Shalev-Shwartz, Shamir, Srebro, and Sridharan (14), and subsequently
Feldman (8), demonstrated how the choice of an algorithm is crucial not only
for optimization reasons, but also for generalization reasons. Namely, to
avoid overfitting without careful algorithmic choices, one must use dimension-
dependent sample size. On the other hand, with the correct algorithm, one can
avoid overfitting with far less data points. For this reason, SCO became a
prototypical model for researching _over-paramterization_ (7, 1, 9, 12). These
works aim to understand how can algorithms avoid overfitting, even when the
number of data points is significantly smaller than the number of free
parameters.

In more detail, a classical paradigm for learning is to draw $n$ i.i.d. data
points $z_{1},\ldots,z_{n}$ from an unknown distribution and to optimize the
_empirical risk_ defined as

$\hat{F}(x)=\frac{1}{n}\sum^{n}_{i=1}f(x,z_{i}),$

where $f(x,z)$ is some loss function that measures the performance of
parameter $x$ on the data point $z$. When $n$ is sufficiently large, a
minimizer of $\hat{F}$ should also demonstrate good performance on the
population loss $F(x)=\mathop{\mathbb{missing}}{E}_{z\sim D}[f(x,z)]$. This is
exactly the setting of SCO, expect that SCO makes the additional assumption
that the loss functions are convex (more details are provided below).

It is a well-known fact that in the Probably Approximately Correct framework
(17, 16), all optimization algorithms share the same statistical rate (17, 4).
Namely, the statistical rate of all learning algorithms is the same. And
understanding the rate of _any_ learning algorithm is equivalent, then, to
understanding the rate of any _specific_ ERM. In stochastic convex
optimization, however, not all algorithms are equal. While there are learning
algorithms that perform well with only $n=O\ (\frac{1}{\varepsilon^{2}})$ data
points (14, 5), others must observe at least $\Omega(\frac{d}{\varepsilon})$
points to guarantee good performance where $d$ is the dimension of the
parameter space $x\in\mathbb{R}^{d}$ (8).

And yet, even though separations between the statistical performances of
different ERMs are known, one of the most fundamental questions in stochastic
convex optimization remained unanswered:

what is the worst-case sample complexity of ERMs in SCO?

A standard covering argument (e.g. (13, 2)) shows it to be at most
$\tilde{O}(\frac{d}{\varepsilon^{2}})$. Feldman (8) demonstrated it to be at
least $\Omega(\frac{d}{\varepsilon}+\frac{1}{\varepsilon^{2}})$. The gap
between the lower bound and the upper bound remained open, and was proposed as
an open problem in (8).

###  1.1. Our contribution

We resolve the afforementioned open problem and complete the picture by
proving that the sample complexity of ERMs in SCO is actually at most

$\tilde{O}\left(\frac{d}{\varepsilon}+\frac{1}{\varepsilon^{2}}\right).$

Notice that this bound separates the statistical complexity of ERMs from
uniform convergence. The statistical complexity of uniform convergence is the
number of examples required so that typically for _every_ model in the
parameter space, the empirical loss is close to the true population loss. In
SCO, Feldman (8) provided a lower bound that matches the well-known upper
bound (2, 13) and demonstrated that the statistical complexity of uniform
convergence is $\tilde{\Theta}(\frac{d}{\varepsilon^{2}})$. Our result shows
that, while different ERMs may exhibit different performances, all ERMs are
better than the worst-case uniform convergence rate. Even without algorithmic
assumptions, learning in SCO is easier than uniform convergence (distinctively
from other classical models such as PAC learning).

A second notable aspect of our result is that, usually, the term
$\tfrac{1}{\varepsilon^{2}}$ corresponds to noise or to the agnostic setting
of learning. The term $\tfrac{d}{\varepsilon}$, on the other hand, corresponds
to a realizable setting. It is somewhat surprising that these two different
types of “behaviors” are simultaneously appearing in a single model. In
stochastic convex optimization, the ERM principle somehow intrinsically
combines low dimensional agnostic learning and high-dimensional realizable
learning.

The above result is true for learning bounded convex Lipschitz functions with
respect to an $\ell_{2}$-bounded domain. We generalize our result and analyze
the statistical complexity of ERMs with respect to general norms. For any norm
and its corresponding unit ball $\mathcal{K}$, and for learning bounded convex
Lipschitz functions, the statistical complexity of ERMs with error
$O(\varepsilon)$ is at most

$\tilde{O}\left(\frac{d}{\varepsilon}+\mathrm{Rad}^{-1}_{\mathcal{K}}(\varepsilon)\right),$

where $\mathrm{Rad}^{-1}_{\mathcal{K}}(\varepsilon)$ measures the statistical
complexity of learning over $\mathcal{K}$ when we restrict the observed losses
to be linear. The first term is the dimension-dependent part of the
statistical complexity and is the same for all norms. The second term, which
is the dimension-independent part for the $\ell_{2}$ norm, is not the
classical Rademacher complexity of the full class (“convex functions”), but is
the Rademacher complexity of a smaller class (“linear functions”). The above
result yields a tight bound for the $\ell_{2}$ norm, but also yields tight
bounds for general $\ell_{p}$ norms (Feldman (8) proved matching lower bounds
for $\ell_{p}$ norms).

##  2\. Formal Setup and Main Result

Let us formally state the algorithmic problem we explore. A one-dimensional
illustration appears in Figure 1. We consider a general norm $\|\cdot\|$ on
$\mathbb{R}^{d}$ and its unit ball $\mathcal{K}$. We also consider a general
domain $Z$, which for concreteness we assume to be finite. Our result hold
when $Z$ is infinite, but then one needs to carefully deal with measurability
issues. We refer to (3) for the relevant definitions and formal setup in which
our result hold in full generality.

For each $z\in Z$, we consider a function $f_{z}(x)$ that is convex and
$L$-Lipschits with respect to $x$. That is, for every $x,y$,

$|f_{z}(x)-f_{z}(y)|\leq L\left\|x-y\right\|.$

We are interested in the problem of optimization over the parameter domain
$\mathcal{K}$. We note, though, that there is no loss of generality in
assuming $f_{z}$ is defined over the whole space $\mathbb{R}^{d}$, because
every $L$-Lipschitz convex function over $\mathcal{K}$ can be extended to an
$L$-Lipschitz convex function over all of $\mathbb{R}^{d}$.

We next assume a distribution $\mathcal{D}$ that is supported on the domain
$Z$. We consider the convex function $F$ defined by

$F(x)=\mathop{\mathbb{missing}}{E}_{z\sim\mathcal{D}}[f_{z}(x)].$

The function $F$ is often referred to as the _population loss_ or _true risk_
, and is also $L$-Lipschitz. The algorithmic goal is to find a minimizer
$x^{\star}$ of $F$. The set of minimizers of $F$ in $\mathcal{K}$ is

$\mathsf{argmin}_{\mathcal{K}}F=\\{x^{\star}\in\mathcal{K}:\forall
x\in\mathcal{K}\ F(x^{\star})\leq F(x)\\}.$

Figure 1. An illustration of a one-dimensional stochastic convex optimization
problem. The gray lines are the graphs of the different $f_{z}$’s. The solid
black line is the target function $F$. The minimizer of $F$ is $x^{\star}=0$.
The dashed line is an example for a possible $\hat{F}$. The minimizer of
$\hat{F}$ is $\hat{x}\approx-0.15$.

The learning algorithm does know the distribution $\mathcal{D}$. Instead, one
assumes that the learner can observe an i.i.d. sample $S=(z_{1},\ldots,z_{n})$
of $n$ examples drawn from the distribution $\mathcal{D}$. A natural strategy
in this setting is to follow the ERM principle. Given $S$, we consider the
_empirical risk_ or _empirical loss_

$\hat{F}=\frac{1}{n}\sum_{j\in[n]}f_{z_{j}}.$

An ERM learning rule is any algorithm that outputs

$\hat{x}\in\mathsf{argmin}_{\mathcal{K}}\hat{F}.$

For an accuracy parameter $\epsilon>0$, the ERM principle is considered
successful if

$F(\hat{x})\leq F(x^{\star})+\varepsilon.$

We would like to have the guarantee that with as few samples as possible, any
algorithm that follows the ERM principle is successful.

Our results provide such a guarantee. We first state our result in the
cleanest form possible. Accordingly, the only two parameters we focus on are
the dimension $d$ and accuracy parameter $\varepsilon$, and we work over the
$\ell_{2}$ norm and its unit ball

$\mathcal{B}=\\{x\in\mathbb{R}^{d}:\|x\|_{2}\leq 1\\}.$

General norms and other parameters are treated in Section 2.1 below.

######  Theorem 1.

Suppose that for every $z\in Z$, the function $f_{z}$ is convex, $1$-Lipschitz
with respect to $\|\cdot\|_{2}$ and for every $x\in\mathcal{B}$ we have
$|f_{z}(x)|\leq 1$. For every distribution $\mathcal{D}$ on $Z$, and for all
accuracy parameters $0<\varepsilon<1$, if

$n\geq
n_{0}=\frac{3d\ln(\frac{40}{\varepsilon})}{\varepsilon}+\frac{40}{\varepsilon^{2}}$

then with probability at least $\frac{3}{4}$ over $S\sim\mathcal{D}^{n}$, for
all $x\in\mathcal{B}$,

$\hat{F}(x)\leq\hat{F}(x^{\star})+\varepsilon\ \ \Longrightarrow\ \ F(x)\leq
F(x^{\star})+40\varepsilon.$

The theorem shows that for $n\geq n_{0}$, not only that the ERM principle is
successful, but it is also robust in the sense that it is safe to output any
point $\hat{x}$ that is merely close to being a minimizer of $\hat{F}$. There
is a distinction between ERMs (algorithms that output a minimizer of
$\hat{F}$) and approximate ERMs (algorithms that output an approximate
minimizer of $\hat{F}$). This subtle distinction is important in SCO.
Approximate ERMs can be more efficient than exact ERMs; see (13). For example,
for $\varepsilon\geq\Omega(1)$, for all problems, sample complexity of $O(1)$
can be achieved by a regularized ERM which is an approximate ERM, but for some
problems, any exact ERM must have sample complexity $\Omega(\ln d)$.

###  2.1. General norms

We next provide a more fine-grained result that generalizes Theorem 1 for
arbitrary norms and their unit balls. We start by introducing the necessary
terminology. Recall that $\left\|\cdot\right\|$ is a norm on $\mathbb{R}^{d}$
and $\mathcal{K}\subset\mathbb{R}^{d}$ is its unit ball. Denote by
$\|\cdot\|_{\star}$ the dual norm

$\left\|g\right\|_{\star}=\sup_{x\in\mathcal{K}}\langle g,x\rangle.$

The Rademacher complexity of $\mathcal{K}$ with respect to a sample
$S=(g_{1},\ldots,g_{n})\in(\mathbb{R}^{d})^{n}$ is

$\displaystyle\mathsf{Rad}(\mathcal{K},S)=\mathop{\mathbb{missing}}{E}_{\sigma}\left[\left\|\frac{1}{n}\sum_{j=1}^{n}\sigma_{j}g_{j}\right\|_{\star}\right],$

where the expectation is over Rademacher random variables
$\sigma_{1},\ldots,\sigma_{n}$ (i.e., i.i.d. uniform in $\\{\pm 1\\}$).
Observe that $\mathsf{Rad}(\mathcal{K},S)$ corresponds to the standard
Rademacher complexity if we think of $\mathcal{K}$ as a class of linear
functions operating on the dual ball; indeed, for every $S$,

$\mathsf{Rad}(\mathcal{K},S)=\mathop{\mathbb{missing}}{E}_{\sigma}\left[\sup_{x\in\mathcal{K}}\frac{1}{n}\sum_{j=1}^{n}\sigma_{j}\langle
g_{j},x\rangle\right].$

For an integer $n$, define

$\mathsf{Rad}(\mathcal{K},n)=\sup_{S}\mathsf{Rad}(\mathcal{K},S),$

where the supremum is over $S=(g_{1},\ldots,g_{n})$ so that
$\|g_{j}\|_{\star}\leq 1$ for all $j\in[n]$. For $\varepsilon>0$, define

$\mathsf{Rad}_{\mathcal{K}}^{-1}(\varepsilon)=\min\big{\\{}n\in\mathbb{N}:\mathsf{Rad}(\mathcal{K},n)<\varepsilon\big{\\}}.$

It is worth noting that because

$\displaystyle\mathop{\mathbb{missing}}{E}\left[\left\|\frac{1}{n+1}\sum_{j=1}^{n+1}\sigma_{j}g_{j}\right\|_{\star}\right]$
$\displaystyle=\mathop{\mathbb{missing}}{E}\left[\left\|\frac{1}{n+1}\sum_{I\subset[n+1]:|I|=n}\frac{1}{n}\sum_{i\in
I}\sigma_{j}g_{j}\right\|_{\star}\right]$
$\displaystyle\leq\frac{1}{n+1}\sum_{I\subset[n+1]:|I|=n}\mathop{\mathbb{missing}}{E}\left[\left\|\frac{1}{n}\sum_{i\in
I}\sigma_{j}g_{j}\right\|_{\star}\right],$

the following monotonicity holds:

$\mathsf{Rad}(\mathcal{K},n+1)\leq\mathsf{Rad}(\mathcal{K},n).$

Therefore, if $n\geq\mathsf{Rad}_{\mathcal{K}}^{-1}(\varepsilon)$ then
$\mathsf{Rad}(\mathcal{K},n)<\varepsilon$.

The general bound on the sample complexity of ERMs is described in the
following theorem.

######  Theorem 2.

Suppose that for every $z\in Z$, the function $f_{z}$ is convex, $L$-Lipschitz
with respect to $\|\cdot\|$ and for every $x\in\mathcal{K}$ we have
$|f_{z}(x)|\leq c$. For every distribution $\mathcal{D}$ on $Z$, and for all
$0<\varepsilon,\delta<1$, if

$n\geq
n_{0}=\frac{12cd}{\varepsilon}\ln\Big{(}\frac{3L}{\varepsilon}\Big{)}+\mathsf{Rad}_{\mathcal{K}}^{-1}\Big{(}\frac{\varepsilon}{2L}\Big{)}+\frac{8c^{2}}{\varepsilon^{2}}\ln\Big{(}\frac{4}{\delta}\Big{)}$

then with probability at least $1-\delta$ over $S\sim\mathcal{D}^{n}$, for all
$x\in\mathcal{K}$,

$\hat{F}(x)\leq\hat{F}(x^{\star})+\varepsilon\ \ \Longrightarrow\ \ F(x)\leq
F(x^{\star})+40\varepsilon.$

The sample complexity $n_{0}$ consists of three different terms. The first
term is of the form $\frac{cd}{\varepsilon}\ln(\frac{L}{\varepsilon})$, and
also appears in the $\ell_{2}$ setting. In a nutshell, the
$d\ln(\frac{L}{\varepsilon})$ part comes from the logarithm of the cover
number (see Lemma 4 below). The second term
$\mathsf{Rad}_{\mathcal{K}}^{-1}\big{(}\frac{\varepsilon}{L}\big{)}$
correspond to learning the special case of linear functions. It heavily
depends on the norm and its unit ball $\mathcal{K}$. For example, when
$\frac{\varepsilon}{L}\geq\Omega(1)$, for the $\ell_{2}$ norm it is $O(1)$,
for the $\ell_{1}$ norm it is $O(\ln d)$, and for the $\ell_{\infty}$ norm it
is $O(d)$. The third term
$O(\frac{c^{2}}{\varepsilon^{2}}\ln(\frac{1}{\delta}))$ is the only place the
confidence parameter $\delta$ appears in.

##  3\. On the proof

We now outline the proof of Theorem 1. The proof has two central ingredients.
One ingredient is a first-order optimality condition for stochastic convex
optimization problems (3 in Section 4.1). The second ingredient connects
properties of ERM to the Bregman divergence and prove a strong concentration
bound for it. The mechanism underlying these steps may be useful for other
convex optimization problems. The proof of the theorem is finally given in
Section 5.1. The proof of Theorem 2 requires a couple of additional ideas,
which are explained in Section 6.

A key property is identified in 7. This claim allows to replace the
$\frac{d}{\varepsilon^{2}}$ term which is “expected to hold” by the term
$\frac{d}{\varepsilon}$ which is “correct”. The intuition for this gain is
that distinguishing between a coin with bias $\frac{1}{2}+\varepsilon$ and a
coin with bias $\frac{1}{2}-\varepsilon$ requires $\frac{1}{\varepsilon^{2}}$
samples, but distinguishing between a coin with bias $\varepsilon$ and a coin
with bias $2\varepsilon$ can be done with only $\frac{1}{\varepsilon}$
samples.

Where is the coin? For the simplicity of the exposition, we assume that the
$f_{z}$’s are smooth and that the minimizer $x^{\star}$ is in the interior of
$\mathcal{B}$ (we also included an illustration in Figure 2). In this case,
$F$ is also smooth and first-order optimality implies that $\nabla
F(x^{\star})=0$. For each $x\in\mathcal{B}$, we know that
$F(x)-F(x^{\star})\geq 0$, and our goal is to control the empirical difference
$\hat{F}(x)-\hat{F}(x^{\star})$. This is achieved, in a nutshell, through the
non-negativity of the Bregman divergence. The Bregman divergence associated
with $f_{z}$ between $x$ and $x^{\star}$ is

$D_{f_{z}}(x,x^{\star}):=f_{z}(x)-f_{z}(x^{\star})-\langle\nabla
f_{z}(x^{\star}),x-x^{\star}\rangle.$

It is always non-negative, and it is also bounded from above by four. The key
observation is that

$F(x)-F(x^{\star})=D_{F}(x,x^{\star})=\mathop{\mathbb{missing}}{E}_{z\sim\mathcal{D}}[D_{f_{z}}(x,x^{\star})],$

which is explained by

$\mathop{\mathbb{missing}}{E}_{z\sim\mathcal{D}}[\nabla
f_{z}(x^{\star})]=\nabla F(x^{\star})=0.$

We also see that “$x$ is a bad output” when $D_{F}(x,x^{\star})\geq
2\varepsilon$. Instead of directly controlling
$\hat{F}(x)-\hat{F}(x^{\star})$, we aim to control the empirical Bregman
divergence

$D_{\hat{F}}(x,x^{\star})=\hat{F}(x)-\hat{F}(x^{\star})-\langle\nabla\hat{F}(x^{\star}),x-x^{\star}\rangle.$

We can think of $D_{F}(x,x^{\star})$ as the bias of a coin taking values in
$[0,4]$. The non-negativity and boundedness of the Bergman divergence allows
to prove, via Bernestein inequality, that if $D_{F}(x,x^{\star})\geq
2\varepsilon$ then

$\Pr[D_{\hat{F}}(x,x^{\star})\leq\varepsilon]\leq\exp(-\Omega(\varepsilon
n)).$

This seems pretty close to our goal; if “$x$ is a bad output” then it is very
likely that $D_{\hat{F}}(x,x^{\star})$ is large. Because we actually care
about $\hat{F}(x)-\hat{F}(x^{\star})$ and not $D_{\hat{F}}(x,x^{\star})$, we
also need to control $\nabla\hat{F}(x^{\star})$. This can be achieved via a
simple concentration argument because

$\mathop{\mathbb{missing}}{E}\big{[}\|\nabla\hat{F}(x^{\star})\|_{2}^{2}\big{]}\leq\frac{1}{n}.$

By taking a standard union bound over an $\varepsilon$-net $N$ for
$\mathcal{B}$ of size $|N|\approx(\tfrac{1}{\varepsilon})^{d}$, we get the
final bound

$\Pr[\exists x\in\mathcal{B}\ F(x)-F(x^{\star})>4\varepsilon,\
\hat{F}(x)-\hat{F}(x^{\star})<\varepsilon]\leq\frac{1}{\varepsilon^{2}n}+|N|\exp(-\Omega(\varepsilon
n)).$

This argument actually works also when the $f_{z}$’s are not assumed to be
smooth. For this, we need to replace “gradients” by “subgradients”; see
Section 4.1 below. But when $x^{\star}$ is on the boundary of $\mathcal{B}$,
even in the smooth case, we do not know that $\nabla F(x^{\star})=0$. In this
case, we additionally need to understand what happens when
$D_{F}(x,x^{\star})<2\varepsilon$. This is achieved in 5.

Figure 2. An illustration of the role the Bregman divergence plays in the
proof. The graphs of $F$ and $\hat{F}$ are from Figure 1. The solid line is
the tangent to $F$ at $x^{\star}=0$, and the dashed line is the tangent to
$\hat{F}$ at $x^{\star}$. The tangents are always below the graphs due to
convexity. The differences between the graphs and the tangents are the Bregman
divergences. By controlling the tangent to $\hat{F}$, we can control the
behavior of ERM. Controlling the tangent to $\hat{F}$ is easier than
controlling $\hat{F}$ because it is an affine function.

##  4\. Preliminaries

We next develop several preliminary results, and provide the background needed
for the proof.

###  4.1. First-order optimality

The subgradient of $f:\mathbb{R}^{d}\to\mathbb{R}$ at $x\in\mathbb{R}^{d}$ is

$\partial f(x)=\\{g\in\mathbb{R}^{d}:\forall y\in\mathbb{R}^{d}\ f(y)\geq
f(x)+\langle g,y-x\rangle\\}.$

If $f$ is convex then the set $\partial f(x)$ is never empty (11). If $f$ is
convex and $L$-Lipschitz with respect to $\|\cdot\|$ then

$g\in\partial f(x)\ \Longrightarrow\ \|g\|_{\star}\leq L.$

A deep property of stochastic functions follows from the subgradient sum
property (because it is a central idea, we included a proof in Appendix A).
For a stochastic convex function, the subgradient can be thought as the
expectation of the subgradients (3); namely, if
$F=\mathop{\mathbb{missing}}{E}_{z\sim\mathcal{D}}[f_{z}],$ then for every
$g\in\partial F(x)$, for each $z\in Z$, there exists $g_{z}\in\partial
f_{z}(x)$ so that

$g=\mathop{\mathbb{missing}}{E}_{z\sim\mathcal{D}}[g_{z}].$

This leads to the following stochastic first-order optimality condition.

######  Proposition 3 (Stochastic first-order condition).

Let $\|\cdot\|$ be a norm on $\mathbb{R}^{d}$ and denote by $\mathcal{K}$ its
unit ball. Let $\mathcal{D}$ be a distribution on the finite set $Z$. Suppose
that for every $z\in Z$, the function $f_{z}$ is convex and $L$-Lipschitz.
Assume that

$x^{\star}\in\mathsf{argmin}_{\mathcal{K}}F$

where $F=\mathop{\mathbb{missing}}{E}_{z\sim\mathcal{D}}[f_{z}]$. Then, for
each $z\in Z$, there is $g_{z}\in\partial f_{z}(x^{\star})$ so that
$\|g_{z}\|_{\star}\leq L$ and for all $x\in\mathcal{K}$,

(4.1) $\langle G,x-x^{\star}\rangle\geq 0$

where $G=\mathop{\mathbb{missing}}{E}_{z\sim\mathcal{D}}[g_{z}]\in\partial
F(x^{\star})$.

###### Proof.

The first-order optimality condition (see e.g. (11, 6)) applied to $F$ states
that there is $G\in\partial F(x^{\star})$ so that for all $x\in\mathcal{K}$,

$\langle G,x-x^{\star}\rangle\geq 0.$

By the subgradient sum property, there are $g_{z}\in\partial f_{z}(x)$ such
that $G=\mathop{\mathbb{missing}}{E}[g_{z}]$. Because $f_{z}$ is
$L$-Lipschitz, we know that $\|g_{z}\|_{\star}\leq L$. ∎

###  4.2. The Bregman divergence

The Bregman divergence measures the difference between a convex function and
its first-order approximation. It is often defined for smooth functions, but
for our purposes, we require a definition that makes sense for genercal SCO
problems. For a stochastic function
$F=\mathop{\mathbb{missing}}{E}_{z\sim\mathcal{D}}[f_{z}]$ and a point
$x^{\star}$, the Bregman divergence associated with $F$ at $x^{\star}$ is

$D(x,x^{\star})=D_{F}(x,x^{\star})=F(x)-F(x^{\star})-\langle
G,x-x^{\star}\rangle,$

for some $G\in\partial F(x^{\star})$. This mapping depends on the choice of
$G$, but to avoid cumbersome notations we will suppress this dependence.
Importantly, we care about the Bregman divergence at $x^{\star}$ which is a
minimizer of $F$, and we assume that $G\in\partial F(x^{\star})$ is chosen to
be a sub-gradient whose existence is guaranteed by 3.

Given a sample $S=(z_{1},\ldots,z_{n})$, the empirical Bregman divergence is

$\hat{D}(x,x^{\star})=\hat{F}(x)-\hat{F}(x^{\star})-\langle\hat{G},x-x^{\star}\rangle,$

where
$\hat{G}=\frac{1}{n}\sum_{i=1}^{n}g_{z_{i}}\in\partial\hat{F}(x^{\star})$. Two
key observations are that by the convexity of all the $f_{z}$’s, both
$D(x,x^{\star})$ and $\hat{D}(x,x^{\star})$ are non-negative, and

$\mathop{\mathbb{missing}}{E}_{S\sim\mathcal{D}^{n}}[\hat{D}(x,x^{\star})]=D(x,x^{\star}).$

###  4.3. Covering numbers

For $\varepsilon>0$, the $\varepsilon$-cover number
$\mathsf{Cov}_{\mathcal{K}}(\varepsilon)$ of $\mathcal{K}$ is the minimum
integer $m$ so that there is a net $N\subset\mathcal{K}$ of cardinality
$|N|=m$ so that for every $x\in\mathcal{K}$ there is $y\in N$ so that
$\|x-y\|\leq\varepsilon$. The following is a standard bound on the cover
numbers of unit balls of norms.

######  Lemma 4.

Let $\|\cdot\|$ be a norm on $\mathbb{R}^{d}$ and denote by $\mathcal{K}$ its
unit ball. For every $\varepsilon>0$,

$\mathsf{Cov}_{\mathcal{K}}(\varepsilon)\leq\Big{(}\frac{2(1+\varepsilon)}{\varepsilon}\Big{)}^{d}.$

###### Proof.

Let $Y$ be a subset of $\mathcal{K}$ of maximum size so that for every $y\neq
y^{\prime}$ in $Y$ we have $\|y-y^{\prime}\|>\varepsilon$. It follows that

$\displaystyle(1+\varepsilon)^{d}|\mathcal{K}|$
$\displaystyle=|(1+\varepsilon)\mathcal{K}|$
$\displaystyle\geq\Big{|}\bigcup_{y\in
Y}\Big{(}y+\frac{\varepsilon}{2}\mathcal{K}\Big{)}\Big{|}$
$\displaystyle=|Y|\cdot\Big{|}\frac{\varepsilon}{2}\mathcal{K}\Big{|}=\Big{(}\frac{\varepsilon}{2}\Big{)}^{d}\cdot|Y|\cdot|\mathcal{K}|,$

where $|\cdot|$ denotes volume. Because $Y$ is maximal, for every
$x\in\mathcal{K}$ there is $y\in Y$ so that $\|x-y\|\leq 2\varepsilon$. ∎

###  4.4. Bernstein’s inequality

Finally, we recall the following concentration bound, due to Bernstein:

######  Lemma (Bernstein’s inequality).

Let $R_{1},\ldots,R_{n}$ be i.i.d. random variables taking values in $[-M,M]$,
each with mean zero and variance $\sigma^{2}$. Then, for all $t>0$, we have

$\Pr\big{[}\sum_{j\in[n]}R_{j}\geq
t\big{]}\leq\exp\Big{(}-\frac{t^{2}}{2\sigma^{2}n+(2Mt/3)}\Big{)}.$

##  5\. The Euclidean norm

In this section, we prove Theorem 1. Let $x^{\star}$ be an arbitrary minimizer
of $F$ in $\mathcal{B}$. Let $G\in\partial F(x^{\star})$ be the subgradient
given in 3. For a fixed sample, we also denote:

$\hat{G}=\frac{1}{n}\sum_{i=1}^{n}g_{z_{i}}.$

We start the proof by providing both a lower bound on the Bregman divergence
at spurious empirical risk minimizers, as well as an upper bound for the
empirical Bregman divergence at empirical risk minimizers.

The following claim says that for a point to be a spurious risk minimizer, the
Bregman divergence must be “large”.

######  Claim 5.

For all $x\in\mathcal{B}$, if

$\hat{F}(x)-\hat{F}(x^{\star})\leq 5\varepsilon$

and

$\displaystyle\|\hat{G}-G\|_{2}\leq\varepsilon$

then

$\displaystyle D(x,x^{\star})\geq F(x)-F(x^{\star})-7\varepsilon.$

###### Proof.

Because

$\displaystyle\langle G,x-x^{\star}\rangle$ $\displaystyle=\langle
G-\hat{G},x-x^{\star}\rangle+\langle\hat{G},x-x^{\star}\rangle$
$\displaystyle\leq 2\varepsilon+\langle\hat{G},x-x^{\star}\rangle$
$\displaystyle=2\varepsilon+\hat{F}(x^{\star})+\langle\hat{G},x-x^{\star}\rangle-\hat{F}(x^{\star})$
$\displaystyle=2\varepsilon+\hat{F}(x)-D(x,x^{\star})-\hat{F}(x^{\star})$
$\displaystyle\leq 2\varepsilon+\hat{F}(x)-\hat{F}(x^{\star})$
$\displaystyle\hat{D}(x,x^{\star})\geq 0$ $\displaystyle\leq 7\varepsilon,$

we can bound

$\displaystyle D(x,x^{\star})$ $\displaystyle=F(x)-F(x^{\star})-\langle
G,x-x^{\star}\rangle$ $\displaystyle\geq F(x)-F(x^{\star})-7\varepsilon.$

∎

Next, we relate data of the form “$x$ is an ERM” to an upper bound on the
empirical Bregman divergence.

######  Claim 6.

For all $x\in\mathcal{B}$, if

$\displaystyle\hat{F}(x)-\hat{F}(x^{\star})\leq 5\varepsilon$

and

$\displaystyle\|\hat{G}-G\|_{2}\leq\varepsilon$

then

$\displaystyle\hat{D}(x,x^{\star})\leq 7\varepsilon.$

###### Proof.

$\displaystyle\hat{D}(x,x^{\star})$
$\displaystyle=\hat{F}(x)-\hat{F}(x^{\star})-\langle\hat{G},x-x^{\star}\rangle$
$\displaystyle\leq 5\epsilon-\langle\hat{G},x-x^{\star}\rangle$
$\displaystyle=5\epsilon-\langle\hat{G}-G,x-x^{\star}\rangle-\langle
G,x-x^{\star}\rangle$ $\displaystyle\leq
5\epsilon-\langle\hat{G}-G,x-x^{\star}\rangle$ $\displaystyle\leq 7\epsilon.$

∎

So far, we showed that for a point to be a spurious empirical risk minimizer,
the Bregman divergence must be large yet the empirical Bregman divergence is
small. The last claim we need is a concentration bound that relates the
empirical and true Bregman divergences.

######  Claim 7.

Suppose that for each $z\in Z$, the function $f_{z}$ is convex, $1$-Lipschitz
with respect to $\|\cdot\|_{2}$, and for all $x\in\mathcal{B}$ we have
$|f_{z}(x)|\leq 1$. Then, for every $x\in\mathcal{B}$,

$\Pr\Big{[}\hat{D}(x,x^{\star})\leq\frac{D(x,x^{\star})}{2}\Big{]}\leq\exp\Big{(}-\frac{D(x,x^{\star})n}{40}\Big{)},$

where the probability is over $z_{1},\ldots,z_{n}$ i.i.d. samples from
$\mathcal{D}$.

###### Proof.

The random variable

$\displaystyle\hat{D}(x,x^{\star})=\frac{1}{n}\sum_{j}D_{z_{j}}(x,x^{\star})$

is the average of $n$ i.i.d. variables $R_{1},\ldots,R_{n}$, each taking
values in $[0,4]$ with expectation $\lambda:=D(x,x^{\star})$. By the
Bhatia–Davis inequality, the variance of the random variables is at most

$(4-\lambda)\lambda\leq 4\lambda.$

By Bernstein’s inequality,

$\displaystyle\Pr\Big{[}\hat{D}(x,x^{\star})\leq\frac{\lambda}{2}\Big{]}$
$\displaystyle=\Pr\Big{[}\sum_{j}(R_{j}-\lambda)\leq-\frac{\lambda
n}{2}\Big{]}$ $\displaystyle\leq\exp\Big{(}-\frac{\lambda^{2}n^{2}}{4(8\lambda
n+2\lambda n)}\Big{)}$ $\displaystyle\leq\exp\Big{(}-\frac{\lambda
n}{40}\Big{)}.$

∎

###  5.1. Putting it together

Assume that $n\geq n_{0}$. We start with a simple claim that controls the
behavior of the linear part, and we show that:

(5.1)
$\Pr[\|\hat{G}-G\|^{2}_{2}>\varepsilon^{2}]\leq\frac{4}{\varepsilon^{2}n}.$

Indeed,

$\displaystyle\mathop{\mathbb{missing}}{E}\|\hat{G}-G\|^{2}_{2}$
$\displaystyle=\frac{1}{n^{2}}\sum_{j,j^{\prime}}\mathop{\mathbb{missing}}{E}\langle
g_{z_{j}}-G,g_{z_{j^{\prime}}}-G\rangle$
$\displaystyle=\frac{1}{n^{2}}\sum_{j}\mathop{\mathbb{missing}}{E}\|g_{z_{j}}-G\|^{2}$
$\displaystyle\leq\frac{4}{n}.$

Now, Eq. 5.1 follows from Markov’s inequality.

Next, denote by $E$ the event that there is $x\in\mathcal{B}$ so that

$\hat{F}(x)-\hat{F}(x^{\star})\leq\varepsilon$

but

$F(x)-F(x^{\star})>40\varepsilon.$

To prove the final result, we need to show that

(5.2) $\Pr(E)\leq\frac{1}{4}.$

Towards this, denote by $H$ the event that

$\displaystyle\|\hat{G}-G\|_{2}\leq\varepsilon.$

Next, let $N$ be an $\frac{\varepsilon}{3}$-net for $\mathcal{B}$ of size at
most $(12/\varepsilon)^{d}$. Denote by $\hat{N}$ the set of points $x\in N$ so
that

$\hat{F}(x)-\hat{F}(x^{\star})\leq 5\varepsilon$

but

$F(x)-F(x^{\star})>35\varepsilon.$

Because $F$ and $\hat{F}$ are Lipschitz, the net property implies that if $E$
holds then $\hat{N}$ is a non-empty set. By 5, conditioned on $H$, if
$x\in\hat{N}$ then

$D(x,x^{\star})\geq 16\varepsilon.$

On the other hand, for every $x$, conditioned on $H$, if $x\in\hat{N}$ then by
6 we have

$\hat{D}(x,x^{\star})\leq 8\varepsilon.$

Let $E_{x}$ be the event that $\hat{D}(x,x^{\star})\leq 8\varepsilon$. We
obtain, therefore:

$E\cap H\subseteq\bigcup_{x\in N:D(x,x^{\star})>16\varepsilon}E_{x}.$

By 7, if $D(x,x^{\star})>16\varepsilon$ then

$\Pr[E_{x}]\leq\exp\Big{(}-\frac{\varepsilon n}{3}\Big{)}.$

By the union bound, Lemma 4, Eq. 5.1, and because $n\geq n_{0}$,

$\displaystyle\Pr[E]$ $\displaystyle\leq\Pr[\neg
H]+|N|\exp\Big{(}-\frac{\varepsilon n}{3}\Big{)}$
$\displaystyle\leq\frac{4}{\varepsilon^{2}n}+\Big{(}\frac{12}{\varepsilon}\Big{)}^{d}\exp\Big{(}-\frac{\varepsilon
n}{3}\Big{)}$ $\displaystyle\leq\frac{1}{4}.$

This completes the proof of Theorem 1.

##  6\. General norms

In this section, we prove Theorem 2. Our first task is to handle the Lipschitz
constant $L$ and the bound $c$ on the $\ell_{\infty}$ norm. To properly handle
general $L$ and $c$, we need to introduce a truncated version of the Bregman
divergence. Second, we address general confidence parameters. This requires a
a uniform concentration result for the gradient at the optimum, combined with
an additional argument that bounds a contractive term that may depend on it.

For the rest of this section, we fix a norm $\|\cdot\|$ and its unit ball
$\mathcal{K}$. We also fix an optimal point $x^{\star}$, and using 3 we fix
subgradients $g_{z}\in\partial f_{z}(x^{\star})$ such that the first-order
condition Eq. 4.1 holds for
$G=\mathop{\mathbb{missing}}{E}_{z\sim\mathcal{D}}[g_{z}]$. As before, we
denote by $\hat{G}$ the empirical subgradient

$\hat{G}=\tfrac{1}{n}\sum_{j=1}^{n}g_{z_{j}}.$

###  6.1. The Lipschitz and $\ell_{\infty}$ constants

Special care is required when $c\ll L$. The reason is that the Bregman
divergence can be as large as $L$ regardless of $c$. We, therefore, introduce
a truncated version of the Bregman divergence. The truncated divergence
associated with $f:\mathcal{K}\to[-c,c]$ is

$T_{f}(x,x^{\star})=f(x)-f(x^{\star})-\max\\{-2c,\langle
g,x-x^{\star}\rangle\\}.$

The truncated divergence, as the Bregman divergence, is always non-negative.
But, in contrast to the Bregman divergence, it is always at most $4c$ because
$f$ is bounded by $c$. Similarly to the Bregman divergence, we use the
following notation:

$T_{z}=T_{f_{z}},\ T=\mathop{\mathbb{missing}}{E}_{z\sim\mathcal{D}}T_{z}\ \
\text{and}\ \ \hat{T}=\frac{1}{n}\sum_{j=1}^{n}T_{z_{j}}.$

The random variable $\hat{T}(x,x^{\star})$ is the average of $n$ i.i.d.
variables taking values in $[0,4c]$ with expectation $T(x,x^{\star})$.
Analogously to 7, we can deduce that:

######  Claim 8.

For every $x\in\mathcal{K}$,

$\Pr\Big{[}\hat{T}(x,x^{\star})\leq\frac{T(x,x^{\star})}{2}\Big{]}\leq\exp\Big{(}-\frac{T(x,x^{\star})n}{40c}\Big{)}.$

We now want to develop analgoue statements to 5 and 6. For that it will be
convenient to add the following notation

(6.1) $\ell_{g}(a)=\max\\{-2c,a-\langle g,x^{\star}\rangle\\}.$

The function $\ell_{g}:\mathbb{R}\to\mathbb{R}$ is always convex and
$1$-Lipschitz. Denote by $\mathcal{L}$ and $\hat{\mathcal{L}}$ the following
functions:

$\mathcal{L}(x)=\mathop{\mathbb{missing}}{E}_{z\sim\mathcal{D}}[\ell_{g_{z}}(\langle
g_{z},x\rangle)]\quad\mathrm{and}\quad\hat{\mathcal{L}}(x)=\frac{1}{n}\sum_{j=1}^{n}\ell_{g_{z_{j}}}(\langle
g_{z_{j}},x\rangle).$

Both $\mathcal{L}$ and $\hat{\mathcal{L}}$ are convex. For a sample
$S=(z_{1},\ldots,z_{n})$, the representativeness111That is the terminology
from the book (13). of $S$ is defined to be

$\mathsf{Rep}(S)=\sup_{x\in\mathcal{K}}(\mathcal{L}(x)-\hat{\mathcal{L}}(x)).$

######  Claim 9.

Suppose that $\mathsf{Rep}(S)\leq 2\varepsilon$. Then, for every
$x\in\mathcal{K}$, if

$\displaystyle\hat{F}(x)-\hat{F}(x^{\star})\leq 6\varepsilon$

then

$\hat{T}(x,x^{\star})\leq 8\varepsilon.$

###### Proof.

$\displaystyle\hat{T}(x,x^{\star})$
$\displaystyle=\hat{F}(x)-\hat{F}(x^{\star})-\hat{\mathcal{L}}(x)$
$\displaystyle\leq
6\varepsilon+\mathcal{L}(x)-\hat{\mathcal{L}}(x)-\mathcal{L}(x)$
$\displaystyle\mathsf{Rep}(S)\leq 2\varepsilon$ $\displaystyle\leq
8\varepsilon-\mathop{\mathbb{missing}}{E}_{z\sim\mathcal{D}}\max\\{-2c,\langle
g_{z},x-x^{\star}\rangle\\}$ $\displaystyle\leq
8\varepsilon-\max\\{-2c,\mathop{\mathbb{missing}}{E}_{z\sim\mathcal{D}}\langle
g_{z},x-x^{\star}\rangle\\}$ $\displaystyle\leq 8\varepsilon-\langle
G,x-x^{\star}\rangle$ $\displaystyle\leq 8\varepsilon.$

∎

######  Claim 10.

Suppose that $\mathsf{Rep}(S)\leq 2\varepsilon$. For all $x\in\mathcal{K}$ if

$\hat{F}(x)-\hat{F}(x^{\star})\leq 5\varepsilon$

then

$\displaystyle T(x,x^{\star})\geq F(x)-F(x^{\star})-7\varepsilon.$

###### Proof.

Because

$\displaystyle\mathcal{L}(x)$
$\displaystyle=\mathcal{L}(x)-\hat{\mathcal{L}}(x)+\hat{\mathcal{L}}(x)$
$\displaystyle\mathsf{Rep}(S)\leq 2\varepsilon$ $\displaystyle\leq
2\varepsilon+\hat{\mathcal{L}}(x)$
$\displaystyle=2\varepsilon+\hat{F}(x^{\star})+\hat{\mathcal{L}}(x)-\hat{F}(x^{\star})$
$\displaystyle\leq
2\varepsilon+\hat{F}(x)-\hat{T}(x,x^{\star})-\hat{F}(x^{\star})$
$\displaystyle\leq 2\varepsilon+\hat{F}(x)-\hat{F}(x^{\star})$
$\displaystyle\hat{T}(x,x^{\star})\geq 0$ $\displaystyle\leq 7\varepsilon,$

we can bound

$\displaystyle T(x,x^{\star})$
$\displaystyle=F(x)-F(x^{\star})-\mathcal{L}(x)$ $\displaystyle\geq
F(x)-F(x^{\star})-7\varepsilon.$

∎

###  6.2. The linear part

In this section, we explain how to control $\mathsf{Rep}(S)$. We are going to
use standard results on the Rademacher complexity, and for that we use the
book (13). In the book, the Rademacher complexity of a set
$A\subset\mathbb{R}^{n}$ is defined to be (and denoted by $R$):

$\mathsf{Rad}(A)=\mathop{\mathbb{missing}}{E}_{\sigma}\left[\sup_{a\in
A}\frac{1}{n}\sum_{j=1}^{n}\sigma_{j}a_{j}\right].$

For a fixed sample $S=(z_{1},\ldots,z_{n})$, we consider the set

$A=A_{S}=\\{(\langle g_{z_{1}},x\rangle,\ldots,\langle
g_{z_{n}},x\rangle)\in\mathbb{R}^{n}:x\in\mathcal{K}\\}$

so that

$\mathsf{Rad}(A)=\mathsf{Rad}(\mathcal{K},S).$

We also use the $1$-Lipschitz maps $\ell_{g}:\mathbb{R}\to\mathbb{R}$ that are
defined in Eq. 6.1. We denote by $\ell=\ell_{S}$ the sequence
$\ell=(\ell_{g_{z_{1}}},\ldots,\ell_{g_{z_{n}}})$, and consider the set

$\ell\circ A=\\{(\ell_{g_{z_{1}}}(\langle
g_{z_{1}},x\rangle),\ldots,\ell_{g_{z_{n}}}(\langle
g_{z_{n}},x\rangle))\in\mathbb{R}^{n}:x\in\mathcal{K}\\}.$

It follows from Rademacher calculus (13, see Lemma 26.9 (contraction lemma))
that

(6.2) $\displaystyle\mathsf{Rad}(\ell\circ
A,S)\leq\mathsf{Rad}(A)=\mathsf{Rad}(\mathcal{K},S).$

We also rely on the McDiarmid’s inequality following (see e.g. (13, Lemma
26.4)).

######  Lemma 11 (McDiarmid’s inequality).

Let $h:Z^{n}\to\mathbb{R}$ be so that for some $c_{0}>0$, for all $j\in[n]$
and for all $z_{1},\ldots,z_{n},z^{\prime}_{i}\in Z$,

(6.3)
$\displaystyle|h(z_{1},\ldots,z_{n})-h(z_{1},\ldots,z_{i-1},z^{\prime}_{i},z_{i+1},\ldots,z_{n})|\leq
c_{0}.$

Let $\mathcal{D}$ be a distribution on $Z$. Then, for all $\delta>0$,

$\Pr_{S\sim\mathcal{D}^{n}}\left[|h(S)-\mu|>c_{0}\sqrt{\frac{\ln(2/\delta)n}{2}}\right]\leq\delta$

where $\mu=\mathop{\mathbb{missing}}{E}_{S\sim\mathcal{D}^{n}}[h(S)]$.

We obtain the following important corollary (see also (13, Theorem 26.5)).

######  Corollary 1.

Suppose that for each $z\in Z$, the function $f_{z}$ is convex and
$L$-Lipschitz with respect to $\|\cdot\|$ and for every $x\in\mathcal{K}$, we
have $|f_{z}(x)|\leq c$. For every distribution $\mathcal{D}$ over $Z$ and
$\delta\geq 0$, with probability at least $1-\delta$ over
$S\sim\mathcal{D}^{n}$,

$\mathsf{Rep}(S)\leq
2L\cdot\mathsf{Rad}(\mathcal{K},n)+c\sqrt{\frac{2\ln(2/\delta)}{n}}.$

###### Proof.

For each $z\in Z$, we have $|\ell_{g_{z}}(x)|\leq 4c$ for all
$x\in\mathcal{K}$. The map $S\mapsto\mathsf{Rep}(S)$ satisfies Eq. 6.3 with
$c_{0}=\frac{2c}{n}$. By Eq. 6.2 and (13, Lemma 26.2), because
$\|g_{z}\|_{\star}\leq L$ for all $z\in Z$,

$\displaystyle\mathop{\mathbb{missing}}{E}_{S\sim\mathcal{D}^{n}}[\mathsf{Rep}(S)]\leq
2\mathop{\mathbb{missing}}{E}_{S\sim\mathcal{D}^{n}}[\mathsf{Rad}(\ell_{S}\circ
A_{S})]\leq 2L\cdot\mathsf{Rad}(\mathcal{K},n).$

By McDiarmid’s inequality, therefore, with probability at least $1-\delta$,

$\mathsf{Rep}(S)\leq
2L\cdot\mathsf{Rad}(\mathcal{K},n)+\frac{2c}{n}\sqrt{\frac{\ln(2/\delta)n}{2}}.$

∎

###  6.3. Putting it together

The proof from here is similar to the simpler setup in Theorem 1. Assume that
$n\geq n_{0}$, as in the theorem statement. Next, denote by $E$ the event that
there is $x\in\mathcal{K}$ so that

$\hat{F}(x)-\hat{F}(x^{\star})\leq\varepsilon$

but

$F(x)-F(x^{\star})>40\varepsilon.$

The final result then follows if we prove that

(6.4) $\Pr(E)\leq\delta.$

Towards this, denote by $H$ the event that

$\displaystyle\mathsf{Rep}(S)\leq 2\varepsilon\ \ $

By Corollary 1,

$\Pr[\neg H]\leq\frac{\delta}{2}.$

Next, let $N$ be an $\frac{\varepsilon}{3L}$-net for $\mathcal{K}$ of minimal
size. Denote by $\hat{N}$ the set of points $x\in N$ so that

$\hat{F}(x)-\hat{F}(x^{\star})\leq 5\varepsilon$

but

$F(x)-F(x^{\star})>35\varepsilon.$

Because $F$ and $\hat{F}$ are Lipschitz, the net property implies that if $E$
holds then $\hat{N}$ is a non-empty set. By 10, conditioned on $H$, if
$x\in\hat{N}$ then

$T(x,x^{\star})\geq 16\varepsilon.$

On the other hand, by 9, for every $x\in\mathcal{K}$, conditioned on $H$, if
$x\in\hat{N}$ then

$\hat{T}(x,x^{\star})\leq 8\varepsilon.$

Let $E_{x}$ be the event that $\hat{T}(x,x^{\star})\leq 8\varepsilon$. We
obtain, then:

$E\cap H\subseteq\bigcup_{x\in N:T(x,x^{\star})>16\varepsilon}E_{x}.$

By 8, if $T(x,x^{\star})>16\varepsilon$ then

$\Pr[E_{x}]\leq\exp\Big{(}-\frac{\varepsilon n}{3c}\Big{)}.$

By the union bound and Lemma 4,

$\displaystyle\Pr[E]$ $\displaystyle\leq\Pr[\neg
H]+|N|\exp\Big{(}-\frac{\varepsilon n}{3c}\Big{)}$
$\displaystyle\leq\frac{\delta}{2}+\Big{(}\frac{12L}{\varepsilon}\Big{)}^{d}\exp\Big{(}-\frac{\varepsilon
n}{3c}\Big{)}.$

The proof of Theorem 2 is now complete because

$\displaystyle\frac{3c^{2}\ln(4/\delta)}{\epsilon^{2}}\geq\frac{3c\ln(2/\delta)}{\epsilon};$

the last inequality is true for $c\geq\varepsilon$, which we can assume
because otherwise the result trivially holds.

## References

  * Amir et al. (2021) Idan Amir, Tomer Koren, and Roi Livni.  SGD generalizes better than GD (and regularization doesn’t help).  In _Conference on Learning Theory_ , pages 63–92. PMLR, 2021.
  * Anthony and Bartlett (1999) Martin Anthony and Peter L Bartlett.  _Neural network learning: Theoretical foundations_ , volume 9.  Cambridge university press, Cambridge, 1999.
  * Bertsekas (1973) Dimitri P. Bertsekas.  Stochastic optimization problems with nondifferentiable cost functionals.  _Journal of Optimization Theory and Applications_ , 12(2):218–231, 1973.
  * Blumer et al. (1989) Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth.  Learnability and the Vapnik-Chervonenkis dimension.  _Journal of the ACM_ , 36(4):929–965, 1989.
  * Bousquet and Elisseeff (2002) Olivier Bousquet and André Elisseeff.  Stability and generalization.  _The Journal of Machine Learning Research_ , 2:499–526, 2002.
  * Bubeck (2015) Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  _Foundations and Trends® in Machine Learning_ , 8(3-4):231–357, 2015.
  * Dauber et al. (2020) Assaf Dauber, Meir Feder, Tomer Koren, and Roi Livni.  Can implicit bias explain generalization? stochastic convex optimization as a case study.  _Advances in Neural Information Processing Systems_ , 33:7743–7753, 2020.
  * Feldman (2016) Vitaly Feldman.  Generalization of erm in stochastic convex optimization: The dimension strikes back.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Koren et al. (2022) Tomer Koren, Roi Livni, Yishay Mansour, and Uri Sherman.  Benign underfitting of stochastic gradient descent.  _Advances in Neural Information Processing Systems_ , 35:19605–19617, 2022.
  * Nemirovski et al. (2009) Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro.  Robust stochastic approximation approach to stochastic programming.  _SIAM Journal on optimization_ , 19(4):1574–1609, 2009.
  * Rockafellar (1997) R. Tyrrell Rockafellar.  _Convex analysis_ , volume 11.  Princeton University Press, 1997.
  * Sekhari et al. (2021) Ayush Sekhari, Karthik Sridharan, and Satyen Kale.  Sgd: The role of implicit regularization, batch-size and multiple-epochs.  _Advances In Neural Information Processing Systems_ , 34:27422–27433, 2021.
  * Shalev-Shwartz and Ben-David (2014) Shai Shalev-Shwartz and Shai Ben-David.  _Understanding machine learning: From theory to algorithms_.  Cambridge university press, 2014.
  * Shalev-Shwartz et al. (2009) Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan.  Stochastic convex optimization.  In _COLT_ , 2009.
  * Shapiro (2003) Alexander Shapiro.  Monte carlo sampling methods.  _Handbooks in operations research and management science_ , 10:353–425, 2003.
  * Valiant (1984) Leslie G Valiant.  A theory of the learnable.  _Communications of the ACM_ , 27(11):1134–1142, 1984.
  * Vapnik and Chervonenkis (2015) Vladimir Vapnik and A. Chervonenkis.  On the uniform convergence of relative frequencies of events to their probabilities.  In _Measures of complexity: festschrift for Alexey Chervonenkis_ , pages 11–30. Springer, 2015.

##  Appendix A The subgradient sum theorem

For completeness, we provide a proof of the subgradient sum theorem (see
Rockafellar’s book (11)). We added a couple of figures that illustrate the
main idea (Figure 4 and Figure 4). We work in the more general setting when
the function is defined on a convex subset of $\mathbb{R}^{d}$. For
$f:\mathcal{K}\to\mathbb{R}$ where $\mathcal{K}\subseteq\mathbb{R}^{d}$ is
convex, define

$\partial_{\mathcal{K}}f(x)=\\{g\in\mathbb{R}^{d}:\forall y\in\mathcal{K}\
f(y)\geq f(x)+\langle g,y-x\rangle\\}.$

######  Theorem (subgradient sum).

Let $\mathcal{K}\subseteq\mathbb{R}^{d}$ be a convex set with non-empty
interior. If $f_{1}:\mathbb{R}^{d}\to\mathbb{R}$ and
$f_{2}:\mathcal{K}\to\mathbb{R}$ are convex and Lipschitz, then for all
$x\in\mathcal{K}$,

$\partial_{\mathcal{K}}(f_{1}+f_{2})(x)=\partial_{\mathbb{R}^{d}}f_{1}(x)+\partial_{\mathcal{K}}f_{2}(x).$

This generality helps, for example, to deduce the first-order optimality
condition we rely on.

######  Claim (first-order optimality).

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ be Lipschitz and convex. Let $\mathcal{K}$
be convex and closed, and let $x_{0}\in\mathsf{argmin}_{\mathcal{K}}f$. Then,
there is $g\in\partial_{\mathbb{R}^{d}}f(x_{0})$ so that $\langle
g,x-x_{0}\rangle\geq 0$ for all $x\in\mathcal{K}$.

###### Proof.

The point $x_{0}$ is also a minimizer of $f+1$ as a function on $\mathcal{K}$.
Therefore, $0\in\partial_{\mathcal{K}}(f+1)(x_{0})$. By the subgradient sum
theorem, there is $g\in\partial_{\mathbb{R}^{d}}f(x_{0})$ so that
$-g\in\partial_{\mathcal{K}}1(x_{0})$. The latter says that for all
$x\in\mathcal{K}$, we have $1\geq 1+\langle-g,x-x_{0}\rangle$. ∎

###### Proof of the subgradient sum theorem.

Let $g\in\partial_{\mathcal{K}}(f_{1}+f_{2})(x)$. Define the convex Lipschitz
functions $h_{1},h_{2}$:

$h_{1}(y)=f_{1}(y)-f_{1}(x)-\langle g,y-x\rangle$

and

$h_{2}(y)=f_{2}(y)-f_{2}(x).$

So, $x$ is a minimizer of $h_{1}+h_{2}$ in $\mathcal{B}$, and
$h_{1}(x)=h_{2}(x)=0$. Define the convex sets

$\displaystyle
Z_{1}=\\{(y_{1},\lambda_{1}):y_{1}\in\mathbb{R}^{d},\lambda_{1}\geq
h_{1}(y_{1})\\}\subset\mathbb{R}^{d}\times\mathbb{R}$

and

$\displaystyle
Z_{2}=\\{(y_{2},\lambda_{2}):y_{2}\in\mathcal{K},\lambda_{2}\leq-
h_{2}(y_{2})\\}\subset\mathbb{R}^{d}\times\mathbb{R}.$

The interiors of these convex sets are disjoint because the minimum of
$h_{1}+h_{2}$ is zero. It follows that there is a hyperplane separating them.
This hyperplane is not “vertical” because the projection of both to
$\mathbb{R}^{d}$ contains $\mathcal{K}$; that is, the separating hyperplane is
a graph of an affine function on $\mathbb{R}^{d}$. The point $(x,0)$ belongs
to both sets, so the hyperplane must contain it. Overall, there is
$v\in\mathbb{R}^{d}$ so that

$\forall(y_{1},\lambda_{1})\in Z_{1}\ \ \ \ \langle
v,y_{1}-x\rangle\leq\lambda_{1}$

and

$\forall(y_{2},\lambda_{2})\in Z_{2}\ \ \ \ \langle
v,y_{2}-x\rangle\geq\lambda_{2}.$

In other words, for all $y\in\mathbb{R}^{d}$,

$\langle v,y-x\rangle\leq h_{1}(y)$

and for all $y\in\mathcal{K}$,

$\langle v,y-x\rangle\geq-h_{2}(y).$

Going back to $f_{1},f_{2}$, we get that for all $y\in\mathbb{R}^{d}$ ,

$\langle v,y-x\rangle\leq f_{1}(y)-f_{1}(x)-\langle g,y-x\rangle$

and for all $y\in\mathcal{K}$

$\langle-v,y-x\rangle\leq f_{2}(y)-f_{2}(x).$

The first inequality says that $g+v\in\partial_{\mathbb{R}^{d}}f_{1}(x)$ and
the second that $-v\in\partial_{\mathcal{K}}f_{2}(x)$. ∎

Figure 3. Part I of the illustration of the proof of the subgradient sum
theorem. The function $f_{1}(x)=(x-0.1)^{2}-\tfrac{1}{25}$ is the gray line.
The function $f_{2}(x)=|x+0.1|$ is the dashed line. Their sum $f_{1}+f_{2}$ is
the solid black line. The point of interest is $x=-\tfrac{1}{10}$, which is
the minimum of $f_{1}+f_{2}$.

Figure 4. Part II of the illustration of the proof of the subgradient sum
theorem. The convex set $Z_{1}$ is the epigraph of $f_{1}$. The convex set
$Z_{2}$ is “minus” the epigraph of $f_{2}$. The point of interest is
$x=-\tfrac{1}{10}$, and $0\in\partial_{\mathcal{B}}(f_{1}+f_{2})(x)$. The two
convex sets meet at $(x,0)$. There is a line separating $Z_{1}$ and $Z_{2}$
going through $(x,0)$. This line shows that we can write $0$ as a subgradient
of $f_{1}$ plus a subgradient of $f_{2}$.


# Finite groups whose maximal subgroups have only soluble proper subgroups

Daria Lytkina
Sobolev Institute of Mathematics SB RAS
Novosibirsk, 630090, Russia
<EMAIL_ADDRESS>
Archil Zhurtov
Kabardino-Balkarian State university
Nalchik, 360004, Russia
<EMAIL_ADDRESS>

###### Abstract

We give a description of a finite group whose maximal subgroups possess only
soluble proper subgroups, which implies the answer to the well-known question
on composition factors of finite groups, whose second maximal subgroups are
soluble.

_Keywords_ Finite group $\cdot$ Maximal subgroup $\cdot$ Solubility

##  1 Introduction

In 1968 J. Thompson published a paper Thompson (1968) containing
classification of minimal simple groups by proving the fact that a finite
simple nonabelian group, all of whose proper subgroups are soluble, is
isomorphic to one of the groups of the following list:

List 1. _Minimal simple nonabelian groups_ :

  1. 1.

$L_{2}(2^{p})$, $p$ is a prime;

  2. 2.

$L_{2}(3^{p})$, $p$ is an odd prime;

  3. 3.

$L_{2}(p)$, $p$ is a prime, $p>3$ and $p\equiv\pm 2\pmod{5}$;

  4. 4.

$Sz(2^{p})$, $p$ is an odd prime;

  5. 5.

$L_{3}(3)$.

NOTE. Throughout, we use the notation from Conway et al. (1985).

The goal of the paper is to get a description of a finite group whose maximal
subgroups possess only soluble proper subgroups.

Of course, the desired result will generalize the mentioned classification
theorem by Thompson. The only difference from the original study is that we
use the classification theorem on finite simple groups stating that every
nonabelian finite simple group is isomorphic to one of the groups from the
following

List 2. _Nonabelian finite simple groups_ :

  1. 1.

One of 27 sporadic groups, including the Tits group ${}^{2}F_{4}(2)^{\prime}$;

  2. 2.

$A_{n}$, $n\geq 5$;

  3. 3.

$L_{n}(q)$, $n\geq 2$,
$(n,q)\notin\\{(2,2),(2,3),(2,4),(2,5),(2,9),(3,2),(4,2)\\}$;

  4. 4.

$U_{n}(q)$, $n\geq 3$, $(n,q)\neq(3,2)$;

  5. 5.

$S_{n}(q)$, $n\geq 4$, $n$ is even, $(n,q)\notin\\{(4,2),(4,3)\\}$;

  6. 6.

$O_{2n-1}(q)$, $O_{2n}^{+}(q)$, $O_{2n}^{-}(q)$, $n\geq 4$;

  7. 7.

$G_{2}(q)$, $q>2$;

  8. 8.

$F_{4}(q)$, $E_{6}(q)$, $E_{7}(q)$, $E_{8}(q)$;

  9. 9.

$Sz(2^{2n+1})$; ${}^{2}G_{2}(3^{2n+1})$; ${}^{2}F_{4}(2^{2n+1})$, $n\geq 1$;
${}^{3}D_{4}(q)$; ${}^{2}E_{6}(q)$.

Note that the list is designed to avoid repetitions. For example, part 3 does
not include groups $L_{2}(4)$ and $L_{2}(5)$ isomorphic with $A_{5}$,
$L_{2}(9)$ isomorphic with $A_{6}$, $L_{4}(2)$ isomorphic with $A_{8}$ and
$L_{3}(2)$ isomorphic with $L_{2}(7)$.

##  2 Main result

THEOREM. Suppose that $G$ is a finite group. Then all proper subgroups of any
of its maximal subgroups are soluble if and only if one of the following
conditions hold:

$(1)$ $G$ is soluble;

$(2)$ $G/\Phi(G)$ is a minimal simple group, i. e. it is isomorphic to one of
the groups from List $1$.

$(3)$ $G$ contains a normal subgroup $G_{0}$ of prime index, and
$G/\Phi(G_{0})$ is a minimal simple group.

$(4)$ $G/\Phi(G)$ is a simple group, isomorphic to one of the groups from the
following List $3$.

List 3.

  1. 1.

$L_{2}(2^{rs})$, $r$ and $s$ are primes;

  2. 2.

$L_{2}(3^{rs})$, $r$ and $s$ are odd primes;

  3. 3.

$L_{2}(p)$, $p$ is a prime and $p\equiv\pm 1\pmod{5}$;

  4. 4.

$L_{2}(p^{r})$, $r$ is an odd prime, $p=5$ or $p$ is a prime, such that
$p\equiv\pm 2\pmod{5}$;

  5. 5.

$L_{2}(9)\simeq A_{6}$, $U_{3}(3)$, $Sz(2^{rs})$, $r$ and $s$ are odd primes.

PROOF. Suppose that case (1) is not true, i. e. $G$ is insoluble. Suppose
first that every of its proper subgroups is soluble. Let $N$ be a maximal
normal subgroup of $G$. Then $\overline{G}=G/N$ is a simple group and $N$ is
soluble. Therefore, $\overline{G}$ is nonabelian, all of its proper subgroups
are soluble, and $\overline{G}$ is isomorphic to one of the groups from List
1. If $M$ is a maximal subgroup of $G$, then $MN\neq G$ and hence $N\leq M$.
So, $N$ is contained in the intersection $\Phi(G)$ of maximal subgroups and
case (2) is true.

Next suppose that $G$ has an insoluble maximal subgroup $M$. If
$M\trianglelefteq G$, then $G/M$ is a group of prime order, all proper
subgroups of $M$ are soluble, and case (3) is true.

And if $G$ has no proper normal insoluble subgroup and $N$ is a maximal in $G$
normal soluble subgroup, then $E=G/N$ is a simple nonabelian group and among
its maximal subgroups there is an insoluble subgroup $M$. By condition all
proper subgroups in $M$ are soluble and, therefore, $M/\Phi(M)$ is a simple
group isomorphic to one of the groups from List 1.

If $MN=G$, then $G/N\simeq M/N\cap M$. Since all proper subgroups of $M$ are
soluble and $G$ has exactly one insoluble composition factor, then all proper
subgroups of $G$ are soluble and, using what we proved before, $G/\Phi(G)$ is
a simple group from List 1. So, $N$ lies in any maximal subgroup of the group
$G$, i.e. $N\leq\Phi(G)$.

Now, to prove the Theorem, it is suffice to confirm the following statement.

Proposition. Let $G$ be a finite simple group containing a proper insoluble
subgroup, and let every such insoluble subgroup modulo its Frattini subgroup
is isomorphic to a group from List $1$. Then $G$ is isomorphic to one of the
groups from List $3$.

Since $G$ is isomorphic to one of the groups from List 2, we have to inspect
this list.

Information about maximal subgroups of sporadic groups provided in Conway et
al. (1985) shows that none of these groups fits to be the group $G$.

Suppose that $G=L_{n}(q)$, $q=p^{s}$, $p$ is a prime, $s\in\mathbb{N}$. If
$n=2$, then by (Huppert, 1979, Satz II,8,27) $G$ is isomorphic to one of the
following groups:

  * •

$L_{2}(2^{rs})$, $r$, $s$ are primes;

  * •

$L_{2}(3^{rs})$, $r$, $s$ are odd primes;

  * •

$L_{2}(p)$, $p\equiv\pm 1\pmod{5}$;

  * •

$L_{2}(p^{r})$, $p=5$ or $p\equiv\pm 2\pmod{5}$, $r$ is an odd prime;

  * •

$L_{2}(9)\simeq A_{6}$.

Note, along the way, that none of the alternating groups $A_{m}$ for $m\geq 7$
satisfies the conditions of the Theorem.

If $n\geq 3$, then the stabilizer $S$ in $G$ of a one-dimensional subspace of
projective space $P_{n-1}$ under natural action of $G$ is isomorphic to
$\left([q^{n-1}]:GL_{n-1}\right)/(q-1,n)$. If $S$ is insoluble, then it does
not satisfy the conditions of the Proposition. It is soluble given $n=2$ and
$q=2$ or $3$. For these two cases $G$ is in List 1.

Another case is when $G=S_{n}(q)$, $n\geq 4$, $n$ is even,
$(n,q)\notin\\{(4,2),(4,3)\\}$. Then the maximal subgroup of the smallest
index in $G$ is insoluble by Mazurov (1993) and does not satisfy the
conditions of the Proposition.

Let $G=U_{n}(q)$.

If $n=3$, then Tables 8.5 and 8.6 from Bray et al. (2013) show that the
conditions of the Proposition are met only by $G=U_{3}(3)$.

If $n=4$, then one of the maximal 2-local subgroups of the group $U_{4}(q)$,
which is isomorphic to $\left([q^{4}]:SL_{2}(q^{2}):(q-1)\right)/(q+1,4)$ is
insoluble and does not satisfy the conditions of the Proposition.

Now, if $n\geq 5$, then the monomial subgroup of $U_{n}(q)$ isomorphic to
$\left((q+1)^{n-1}/(q+1,n)\right):S_{n}$ is insoluble and does not meet the
conditions of the Proposition.

If $G$ is an orthogonal group in dimension at least 7, its subgroup of the
smallest index is insoluble and does not satisfy the conditions of the
Proposition (see Vasil’ev and Mazurov (1994)).

Same is true for exceptional groups of types $F_{4}$, $E_{6}$, $E_{7}$, and
$E_{8}$, and also for groups of the type ${}^{2}E_{6}$ (see Vasil’ev (1996,
1997, 1998)). Maximal subgroups of simple groups of the type $G_{2}$,
$Sz(2^{2n+1})$, ${}^{2}G_{2}(3^{2n+1})$, ${}^{2}F_{4}(2^{2^{2n+1}})$, and
${}^{3}D_{4}(q)$ are listed in Bray et al. (2013) (Tables 8.16, 8.30, 8.41,
8.42, 8.43, 8.51). Except for the groups $Sz(2^{2n+1})$, none of the groups in
those tables satisfies the conditions of the Proposition.

For Suzuki groups, the conditions of the Proposition are met only by the
groups $Sz(2^{rs})$, where $r$ and $s$ are odd primes. This proves the
Proposition along with the Theorem.

The Theorem ovbiously implies the answer to the well-known question on
composition factors of finite groups, whose second maximal subgroups are
soluble.

Corollary. Consider a finite group $G$, such that every maximal subgroup of
its maximal subgroup is soluble. If $C$ is a composition factor of $G$, then
$C$ is either a group of prime order, or $C$ is isomorphic to one of the
groups from List $1$ or List $3$.

## References

  * Thompson (1968) J. G. Thompson.  Nonsolvable finite groups all of whose local subgroups are solvable.  _Bull. AMS_ , 74:383–437, 1968.
  * Conway et al. (1985) J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker, and R.A. Wilson.  _An atlas of finite groups_.  Clarendon Press, Oxford, 1985.
  * Huppert (1979) B. Huppert.  _Endliche Gruppen. I._ Springer Verlag, Berlin, Heidelberg, New York, 1979.
  * Mazurov (1993) V. D. Mazurov.  Minimal permutation representation of finite simple classical groups. Special linear, symplectic, and unitary groups.  _Algebra and Logic_ , 32(3):142–153, 1993.
  * Bray et al. (2013) J. N. Bray, D. F. Holt, and C. M. Roney-Dougal.  _The Maximal Subgroups of the Low-Dimensional Finite Classical Groups_.  Cambridge University Press, Lond. Math. Soc. Lect. Note Ser., 2013.
  * Vasil’ev and Mazurov (1994) A. V. Vasil’ev and V. D. Mazurov.  Minimal permutation representations of finite simple orthogonal groups.  _Algebra and Logic_ , 33(6):337–350, 1994.
  * Vasil’ev (1996) A. V. Vasil’ev.  Minimal permutation representations of finite simple exceptional groups of types $G_{2}$ and $F_{4}$.  _Algebra and Logic_ , 35(6):371–383, 1996.
  * Vasil’ev (1997) A. V. Vasil’ev.  Minimal permutation representations of finite simple exceptional groups of types $E_{6}$, $E_{7}$ and $E_{8}$.  _Algebra and Logic_ , 36(5):302–310, 1997.
  * Vasil’ev (1998) A. V. Vasil’ev.  Minimal permutation representations of finite simple exceptional twisted groups.  _Algebra and Logic_ , 37(1):9–20, 1998.