\section{Introduction}
\label{sec:intro}

Automotive applications like advanced driver's assistance systems often require very large fields of view (FOV) to provide the necessary information about the car's environment.
In video surveillance, where it is also fundamental to survey large areas, an FOV of well beyond the common 40 to 60 degrees typical lenses provide is desirable so that as few cameras as possible may be installed.
Fisheye lenses~\cite{miyamoto1964fel} are capable of achieving an FOV of 180 degrees and more and are thus very much suited to the aforementioned application scenarios.
In automotive applications, fisheye cameras are made use of for lane detection~\cite{auto1} and similar assistance systems~\cite{gehrig2, gehrig}; in surveillance scenarios, object tracking~\cite{surveillance2} and the generation of perspective views~\cite{surveillance} are important aspects.

A typical characteristic of fisheye imagery is the strong radial distortion that is introduced by projecting a hemisphere onto the image plane.
This characteristic is not taken into account by conventional image and video processing algorithms, which may perform poorly when being applied to fisheye data.
As fisheye cameras gain more and more popularity, and are now used also by outdoor enthusiasts (the wide-angle \textit{GoPro} camera is just one example), the need for algorithms adapted to fisheye data thus arises.

\begin{figure}[t]
\small
\label{fig:projections}
\centering
\psfrag{e}[cc][cc]{\small \hspace{0.15cm}Equisolid fisheye, FOV~=~185$^\circ$}
\psfrag{o}[cc][cc]{\small Perspective, FOV~$\approx$~110$^\circ$}
\centerline{\includegraphics[width=0.9\columnwidth]{Figures/checkerFOV}}
\input{models}
\vspace{-0.4cm}
\caption{Top: Comparison of equisolid fisheye FOV and perspective FOV (same sensor size). Bottom: Projections as functions of radius $r$ over incident angle $\theta$ with $f$ = 1.8 mm and $\theta_{\text{max}}$ = 90$^\circ$.}
\vspace{-0.5cm}
\end{figure}

During the development of new image processing algorithms, test data such as the well-known Kodak image set~\cite{kodak} or the Tecnick test images~\cite{tecnick, tecnick2} are frequently used.
For multiview applications, the Middlebury set~\cite{middlebury} is available and for video processing and coding, one might make use of the video set provided by ARRI~\cite{arri} and the HEVC Class A through F test video sequences~\cite{hevctest}, respectively.
When dealing with non-rectilinear imagery, however, one is hard pressed to find freely available data sets similar to those mentioned.
To the best of the authors' knowledge, no such data set exists for fisheye video sequences, either.

Because of this apparent lack of suitable fisheye material, a data set first created by the authors during their previous work on motion estimation and temporal error concealment for fisheye video sequences~\cite{eichenseer2015motionfish, eichenseer2015tecfish}, and significantly extended since, is introduced in this paper and made freely available via their website.
Both synthetically generated and actually captured fisheye video sequences are provided, ranging from simple patterns to more complex scenes, including automotive and surveillance content.
For all sequences, information on the acquisition process as well as further parameters are provided.
Making use of the synthetic sequences especially facilitates the verification and evaluation of new algorithms, since here, all parameters are known and an exact projection function is used so that calibration is unnecessary.
To demonstrate the use of the data set and to show a practical application for our sequences, we revisit our previously published hybrid motion estimation method for fisheye video sequences~\cite{eichenseer2015motionfish} and provide some new results for the synthetic sequences at the end of the paper.

\begin{table}[t]
\small
\caption{Perspective projection and classical fisheye projections.}
\label{tab:projections}
\centering
\renewcommand\arraystretch{0.95}
\begin{tabularx}{\columnwidth}{Xlcc}
\toprule
Projection & Equation & FOV$_{\text{max}}$ & $\theta_{\text{max}}$ \\
\midrule
Perspective & $r = f \tan \theta$ & $\ll$ 180$^{\circ}$ & $\ll$ 90$^{\circ}$ \\
\addlinespace
Equidistant & $r = f\theta$ & $\infty$ & $\infty$ \\
Equisolid & $r = 2f \sin{\left( \theta/2\right)}$ & 360$^{\circ}$ & 180$^{\circ}$ \\
Stereographic & $r = 2f \tan{\left(\theta/2\right)}$ & $\ll$ 360$^{\circ}$ & $\ll$ 180$^{\circ}$\\
Orthographic & $r = f \sin{\theta}$ & 180$^{\circ}$ & 90$^{\circ}$ \\
\bottomrule
\end{tabularx}
\vspace{-0.5cm}
\end{table}

\section{Synthetic Fisheye Video Sequences}
\label{sec:projections}

\begin{table}[t]
\small
\caption{Global \textit{Blender} configuration.}
\label{tab:blender}
\centering
\renewcommand\arraystretch{0.95}
\begin{tabularx}{\columnwidth}{Xl}
\toprule
Engine & Cycles Renderer \\
Lens & Panoramic, Fisheye Equisolid (Equidistant)\\
Focal length & 1.8 mm (not needed for equidistant model) \\
Field of view & 185 degrees \\
Sensor size & 5.20 mm, AUTO (5.81 mm, AUTO) \\
Resolution & 1088 $\times$ 1088 pixels \\
Output & PNG, RGBA, 8 bits, uncompressed \\
Noise pattern & Varying for each frame \\
\bottomrule
\end{tabularx}
\vspace{-0.6cm}
\end{table}
Images and videos captured by conventional cameras follow the pinhole model, i.\,e., a perspective projection is used to map a scene to the image plane.
In contrast to that, fisheye lenses make use of projections which are able to capture a far wider FOV~\cite{miyamoto1964fel,kannala2006genericmodel}. The four classical fisheye projections as well as the perspective projection are compared in Table~\ref{tab:projections}, with $f$, $\theta$, and $r$ denoting the focal length, incident angle of light, and distance to the image center, respectively.
The maximum theoretically possible FOV as well as the corresponding maximum $\theta$ are also given.
Fig.~\ref{fig:projections} visualizes the different projection functions.
Here, the limitations of the pinhole model's FOV become very evident when the distance $r$ is actually interpreted as half the sensor width.
Quite obviously, a large FOV can only be obtained by making use of a fisheye projection.

The classical fisheye projections are given by trigonometrical expressions which can be easily inverted.
To inspect basic characteristics of fisheye images and their behavior in typical image processing algorithms, we thus decided to create synthetic fisheye image sequences so as to have control over the exact underlying model.
As a rendering software, \textit{Blender}~\cite{blender} was employed as it supports perspective as well as panoramic lenses.
For the latter, both equisolid and equidistant fisheye projections are available, which we made use of for our synthetic sequences.
The global settings for the equisolid sequences are summarized in Table~\ref{tab:blender} with differing settings for the equidistant versions denoted in parentheses.
The choice of $f$ = 1.8 mm is due to the actual fisheye lens used for the recording of the real-world sequences.
In order to generate circular equisolid fisheye images, we derived a virtual sensor of size 5.20 by 5.20 mm as this just allows capturing an FOV of 185 degrees when employing the equisolid model: $2r = 2f\sin{(\theta_{\text{max}}/2)} \approx 5.20$, with $\theta_{\text{max}} = \text{FOV}/2$ and $2r$ representing the corresponding sensor width.
For the equidistant model, we require $2r = f\theta_{\text{max}} \approx 5.81$, i.\,e., a sensor size of 5.81 by 5.81 mm.

Table~\ref{tab:charsynth} provides the characteristics of the synthetic sequences.
Fig.~\ref{fig:synthSeq} shows example frames of the majority of those sequences, with synthetic pattern sequences on the left and synthetic scene sequences on the right side.
The former make use of simple patterns such as checkerboards arranged on a cube around a moving fisheye camera, which is identical for sequences A1 through E6 and provides translational motion as well as a horizontal pan, zoom, and vertical pan.
\textit{CheckercubeC}, \textit{CheckercubeD}, \textit{Rays}, \textit{Stars}, and \textit{Lorem} are based on images taken from the artificial image set of the Tecnick~\cite{tecnick} library.
\textit{CheckercubeC} can also be made use of for calibration purposes.
As the underlying model is mathematically exact, it can be used to verify calibration methods based on checkerboard patterns such as~\cite{scara2}.
\textit{Cards}, \textit{Clips}, \textit{Coins}, \textit{Fence}, \textit{Flowers}, and \textit{Pencils} use images taken from the new Tecnick~\cite{tecnick2} image set.

For the synthetic scene sequences, we combined several object models available through~\cite{blendswap} to create suitable scenes.
We then added the fisheye camera, set both camera and object motion as desired, and thus generated more realistic sequences.
The motion between two consecutive frames was generally chosen to be minor.
Therefore, the frame rate should be set to 50 Hz during playback.
Depending on user preference, a lower frame rate (starting from 25 Hz) may also be reasonable.
If needed, the sequences can be temporally subsampled to create more pronounced motion patterns.

\begin{figure*}[t]
\centering
\psfrag{a1}[lt][lt]{\small A2}
\psfrag{a2}[lt][lt]{\small A3}
\psfrag{a3}[lt][lt]{\small H2}
\psfrag{a4}[lt][lt]{\small F1}
\psfrag{a5}[lt][lt]{\small F3}
\psfrag{a6}[lt][lt]{\small B1}
\psfrag{a7}[lt][lt]{\small E2}
\psfrag{a8}[lt][lt]{\small G1}
\psfrag{a9}[lt][lt]{\small G4}
\psfrag{a0}[lt][lt]{\small K1}
\psfrag{o1}[lt][lt]{\small C2}
\psfrag{o2}[lt][lt]{\small E6}
\psfrag{o3}[lt][lt]{\small J1}
\psfrag{o4}[lt][lt]{\small J3}
\psfrag{o5}[lt][lt]{\small J4}
\centerline{\includegraphics[width=0.98\textwidth]{Figures/synthSeq3}}
\vspace{-0.3cm}
\caption{Example images of some of the synthetic equisolid fisheye sequences.}
\label{fig:synthSeq}
\vspace{-0.5cm}
\end{figure*}

\begin{table}[t]
\small
\caption{Characteristics of the synthetic sequences.}
\label{tab:charsynth}
\centering
\renewcommand\arraystretch{0.92}
\begin{tabularx}{\columnwidth}{lXrrll}
\toprule
ID & Name & Frames & Camera & Scene & Motion \\
\midrule
A1 & CheckercubeA & 350 & moving & static & TPZ \\
A2 & CheckercubeB & 350 & moving & static & TPZ \\
A3 & CheckercubeC & 350 & moving & static & TPZ \\
A4 & CheckercubeD & 350 & moving & static & TPZ \\
B1 & Rays & 350 & moving& static & TPZ \\
B2 & Stars & 350 & moving& static & TPZ \\
C1 & Lorem & 350 & moving& static & TPZ \\
C2 & Alphabet & 350 & moving& static & TPZ \\
D1 & Gradient & 350 & moving& static & TPZ \\
E1 & Cards & 350 & moving& static & TPZ \\
E2 & Clips & 350 & moving& static & TPZ \\
E3 & Coins & 350 & moving& static & TPZ \\
E4 & Fence & 350 & moving & static & TPZ \\
E5 & Flowers & 350 & moving & static & TPZ \\
E6 & Pencils & 350 & moving& static & TPZ \\
\addlinespace
F1 & Street & 1800 & moving& static & TZ \\
F2 & CarsA & 121 & static& moving & T \\
F3 & CarsB & 121 & static& moving & T \\
G1 & PoolA & 752 & moving& static & T \\
G2 & PoolB & 748 & moving& static & T \\
G3 & PoolNightA & 320 & moving& moving & TP \\
G4 & PoolNightB & 320 & static& moving & T \\
H1 & Room & 400 & static& moving & T \\
H2 & LivingroomA & 111 & moving & static & R \\
H3 & LivingroomB & 82 & static & moving & T \\
H4 & LivingroomC & 82 & moving & static & T\\
J1 & HallwayA & 600 & moving& static & ZP \\
J2 & HallwayB & 120 & moving& moving & RT \\
J3 & HallwayC & 120 & static & moving & T \\
J4 & HallwayD & 500 & moving & static & TP \\
K1 & PillarsA & 550 & static& moving & T \\
K2 & PillarsB & 550 & static& moving & T \\
K3 & PillarsC & 550 & moving& moving & T \\
\midrule
\multicolumn{6}{r}{\footnotesize T: Translation, Z: Zoom, P: Pan, R: Rotation} \\
\bottomrule
\end{tabularx}
\vspace{-0.6cm}
\end{table}

\section{Real-World Fisheye Video Sequences}

\begin{figure*}[t]
\centering
\psfrag{a1}[cc][cc]{\small TestchartA}
\psfrag{a2}[cc][cc]{\small LabRoomA}
\psfrag{a3}[cc][cc]{\small LibraryA}
\psfrag{a4}[cc][cc]{\small LibraryB}
\psfrag{a5}[cc][cc]{\small ClutterA}
\psfrag{a6}[cc][cc]{\small LectureA}
\psfrag{a7}[cc][cc]{\small CarparkC}
\psfrag{a8}[cc][cc]{\small CarparkB}
\psfrag{a9}[cc][cc]{\small ElevatorA}
\psfrag{a0}[cc][cc]{\small DriveA}
\centerline{\includegraphics[width=\textwidth]{Figures/realScene2}}
\vspace{-0.4cm}
\caption{Example frames of some of the real-world sequences.}
\label{fig:realScene}
\vspace{-0.7cm}
\end{figure*}

Apart from synthetic sequences, the data set also contains a number of real-world sequences that were captured with an actual fisheye camera.
The camera employed was a Basler ace acA2000-50gc which uses a GigE interface for recording up to 50 frames per second with a resolution of 2048$\times$1086 pixels.
The raw output images are saved in 12 bit Bayer GR format.
As a lens, the Fujinon FE185C057HA-1 fisheye was used.
This fixed-focus lens has a focal length of 1.8 mm, a manually operated iris range of F1.4$\sim$F16, and allows capturing an FOV of 185 degrees.
As the camera contains a 2/3~inch sensor, the lens thus creates circular fisheye images.

For our data set, we chose mainly indoor scenes, including surveillance scenarios, as the large FOV easily leads to overexposed areas which are difficult to control.
An advantage of indoor locations is given by the many straight lines that can be found on ceilings, furniture, etc., and as straight lines are indeed not straight when captured with a fisheye camera, they serve as the prime characteristic in almost every sequence.
Despite the difficulty of exposure control, some outdoor sequences were recorded representing automotive and surveillance scenarios.
Both exposure time and aperture were adjusted to the respective lighting conditions and may be taken from Table~\ref{tab:charreal}, where the characteristics of the real-world sequences can be found.
The target frame rate was set to a constant 40 frames per second, but may actually be less than that.
Since the circular fisheye images occupy a roughly square sensor area, all images recorded have a cropped resolution of 1150~$\times$1086~pixels and may be further cropped as needed.
All sequences are provided in both raw image 12 bit TIFF format (sensor data) and in 8 bit PNG format (output data).
For the latter, the AHD~\cite{hirakawa2005ahd} algorithm was employed for demosaicking preceded by white balancing and followed by gamma correction in order to create a pleasing subjective impression of the scene.
Fig.~\ref{fig:realScene} provides example frames for many of the real-world sequences.

Since actual fisheye lenses rarely follow one of the models described in section~\ref{sec:projections}, only a calibration helps to determine the camera parameters.
We thus also provide calibration images in our data set, which can be used with calibration methods that are based on a calibration pattern.
The provided images show a checkerboard pattern at different angles and positions and have been successfully tested for calibration via the OcamCalib Toolbox version 3.0~\cite{scara2}.
The calibration results are made available along with the calibration images

\section{Fisheye Motion Estimation}

As initially motivated, conventional video processing algorithms do not take into account the fisheye characteristics.
Traditional block-matching motion estimation (ME)~\cite{blockmatching}, for example, is based on a translational motion model as this is the assumed predominant kind of motion found in typical video sequences.
Since this kind of ME method works in a block-based manner, it is suited to global and local translational motion alike.
With fisheye video sequences, however, the translational motion model is no longer valid.
In~\cite{eichenseer2015motionfish}, we therefore introduced a hybrid ME technique adapted to equisolid fisheye data which introduces suitable projections based on the equisolid fisheye model so as to be able to exploit the translational model while at the same time taking the fisheye characteristics into consideration.
A small subset of the synthetic sequences presented here has already been used for evaluating this method.
We would now like to provide some additional results and thereby show that it is indeed necessary to adapt conventional image and video processing techniques to fisheye data.
To that end, Table~\ref{tab:psnr} provides a comparison of traditional, translational motion estimation (TME) with our hybrid technique (HME).
The search range and block size employed here were 64 and 16 pixels, respectively.
Details about the algorithm as well as further settings may be taken directly from~\cite{eichenseer2015motionfish}.
With average obtainable gains of up to 2 dB, the need for fisheye adaptations is clearly given and thus, our proposed data set aims at helping develop these adaptations.

\begin{table}[h!]
\small
\caption{Characteristics of the real-world sequences.}
\label{tab:charreal}
\centering
\renewcommand\arraystretch{0.95}
\begin{tabularx}{\columnwidth}{Xrccl}
\toprule
Name & Frames & Camera/Scene: & Exposure & Aper- \\
& & Motion & Time & ture\\
\midrule
TestchartA & 300 & static/moving: T & 10 ms & F4\\
TestchartB & 300 & static/moving: T & 10 ms & F4\\
TestchartC & 500 & static/shaky: T & 10 ms & F4 \\
AlfaA & 500 & static/moving: T & 10 ms & F4\\
AlfaB & 500 & static/moving: T & 10 ms & F4\\
AlfaC & 500 & static/shaky: T & 10 ms & F4 \\
LibraryA & 500 & moving/static: Z & 20 ms & F1.4 \\
LibraryB & 487 & moving/static: T & 20 ms & F1.4 \\
LibraryC & 252 & moving/static: P & 20 ms & F1.4\\
LibraryD & 300 & shaky/static: T & 20 ms & F1.4 \\
LibraryE & 300 & shaky/static: T & 20 ms & F1.4 \\
CarparkA & 302 & static/moving: T & 15 ms & F6\\
CarparkB & 982 & static/moving: T & 15 ms & F6\\
CarparkC & 1387 & static/moving: T & 15 ms & F6 \\
DriveA & 1251 & moving/static: ZP & 1 ms & F6\\
DriveB & 400 & moving/moving: ZPT & 1 ms & F6\\
DriveC & 400 & moving/static: ZP & 1 ms& F6\\
DriveD & 863 & moving/static: TP & 5 ms& F16\\
DriveE & 420 & moving/static: T & 5 ms& F16\\
ElevatorA & 321 & static/moving: T & 15 ms & F4 \\
ElevatorB & 211 & static/moving: T & 15 ms & F4 \\
ElevatorC & 136 & static/moving: T & 15 ms & F4\\
ElevatorD & 216 & static/moving: T & 15 ms & F4\\
LabRoomA & 650 & static/moving: T & 15 ms & F4 \\
LabRoomB & 241 & static/moving: T & 15 ms & F4 \\
ClutterA & 500 & moving/static: T & 30 ms & F1.4 \\
ClutterB & 500 & moving/static: T & 30 ms & F1.4 \\
LectureA & 846 & moving/static: P & 15 ms & F4\\
LectureB & 461 & moving/static: T & 15 ms & F4\\
\addlinespace
Calibration & -- & static/various angles & 15 ms & F4 \\
\midrule
\multicolumn{5}{r}{\footnotesize T: Translation, Z: Zoom, P: Pan} \\
\bottomrule
\end{tabularx}
\vspace{-0.3cm}
\end{table}

\vspace{-0.3cm}
\section{Conclusion}
\label{sec:conclusion}
\vspace{-0.15cm}

This paper introduced a data set of fisheye video sequences that may be used in the development of new image and video processing algorithms designed for fisheye imagery.
While one part of the data set comprises real-world sequences captured with an actual fisheye camera, including material for automotive and video surveillance scenarios, the other part of the set provides synthetic fisheye sequences generated in \textit{Blender}.
Due to their mathematical exactness, the synthetic sequences are especially useful as ground truth data on which novel algorithms may initially be tested.
Parameters like focal length and resolution were chosen such that the synthetic sequence characteristics are very similar to the real-world sequence characteristics.
Any algorithms should thus be very well applicable to both categories of sequences.
For the real-world sequences, calibration images and results are provided so as to allow adaptation to more realistic camera parameters.
The need for fisheye adaptations was demonstrated with a brief excursion into fisheye motion estimation.
Further sequences and ground-truth motion information for the synthetic sequences are currently being worked on and will be progressively made available via the authors' website \texttt{www.lms.lnt.de/fisheyedataset/}.

\begin{table}[t]
\small
\caption{Average luminance PSNR results and gain per sequence.}
\label{tab:psnr}
\centering
\renewcommand\arraystretch{1.0}
\begin{tabularx}{\columnwidth}{lccc}
\toprule
Sequence (frames tested) & HME & TME & Gain \\
\midrule
CheckercubeC (34) & 32.62 dB & 30.59 dB & 2.03 dB \\
Alphabet (34) & 21.33 dB & 19.58 dB & 1.76 dB \\
Rays (34) & 28.08 dB & 26.77 dB & 1.31 dB \\
PoolA (74) & 39.76 dB & 37.85 dB  & 1.91 dB \\
PoolNightA (63) & 35.80 dB& 34.40 dB & 1.40 dB \\
PillarsA (109) & 42.42 dB & 40.74 dB & 1.68 dB \\
\bottomrule
\end{tabularx}
\vspace{-0.4cm}
\end{table}

\section{Acknowledgment}

The authors would like to thank Michael Ortner and Andreas Luder for their work on the synthetic and real-world sequences, respectively.
Detailed credits on the Blender models used may be found on the authors' webpage.
This work was supported by the Research Training Group 1773 “Heterogeneous Image Systems”, funded by the German Research Foundation (DFG).

\bibliographystyle{IEEEbib}


\section{Introduction} \label{sec:intro}

\subsection{Background and Motivation} \label{ssec:background}

A halfspace, or Linear Threshold Function (LTF), is any function $f: \mathbb{R}^m \to \{ \pm 1\}$ of the form
$f(x) = \mathrm{sign}(w \cdot x- \theta)$, for some weight vector $w \in \mathbb{R}^m$ and threshold $\theta \in \mathbb{R}$.
(The function $\mathrm{sign}: \mathbb{R} \to \{ \pm 1\}$ is defined as $\mathrm{sign}(t)=1$ if $t \geq 0$ and $\mathrm{sign}(t)=-1$ otherwise.)
Halfspaces are a fundamental class of Boolean functions that have been extensively studied in
computational complexity and learning theory over several decades~\cite{MinskyPapert:68, Yao:90, GHR:92, CristianiniShaweTaylor:00, AoBF14}. The problem of learning an unknown halfspace is as old
as the field of machine learning, starting with the Perceptron algorithm~\cite{Rosenblatt:58, Novikoff:62},
and has been one of the most influential problems in this field  with techniques
such as SVMs~\cite{Vapnik:98} and AdaBoost~\cite{FreundSchapire:97} coming out of its study.

In the realizable PAC model~\cite{val84}, i.e., when the labels are consistent with the target function,
halfspaces are efficiently learnable via Linear Programming (see, e.g.,~\cite{MT:94}).
In the presence of noisy data, the computational complexity of learning halfspaces depends on
the underlying noise model. Here we study the complexity of learning halfspaces
with Massart noise. In the Massart (or bounded) noise model, the label of each example $x$
is flipped independently with probability $\eta(x) \leq \eta$, for some parameter $\eta \leq 1/2$.
The flipping probability is
bounded above by $1/2$, but can depend on the example $x$ in a potentially adversarial manner.
The following definition encapsulates the PAC learning problem in this noise model.

\begin{definition}[PAC Learning with Massart Noise] \label{def:massart-learning}
Let $\mathcal{C}$ be a concept class of Boolean-valued functions over $X= \mathbb{R}^m$, $D_{x}$
be a fixed but unknown distribution over $X$, and $0 \leq \eta \leq 1/2$ be the noise parameter.
Let $f: X \to \{\pm1\}$ be the unknown target concept with $f \in \mathcal{C}$.
A {\em Massart example oracle}, $\mathrm{EX}^{\mathrm{Mas}}(f, D_{x}, \eta)$,
works as follows: Each time $\mathrm{EX}^{\mathrm{Mas}}(f, D_{x}, \eta)$ is invoked,
it returns a labeled example $(x, y)$, where $x \sim D_{x}$, $y = f(x)$ with
probability $1-\eta(x)$ and $y = -f(x)$ with probability $\eta(x)$,
for some {\em unknown} function $\eta(x): X \to [0, 1/2]$
with $\eta(x)\leq \eta$ for all $x \in X$.
Let $D$ denote the joint distribution on $(x, y)$ generated by the Massart example oracle.
A PAC learning algorithm is given i.i.d.\ samples from $D$
and its goal is to output a hypothesis $h: X \to \{\pm1\}$ such that with high probability
the error $\mathbf{Pr}_{(x, y) \sim D} [h(x) \neq y]$ is as small as possible. We will use
$\mathrm{OPT} \stackrel{{\mathrm {\footnotesize def}}}{=} \inf_{g \in \mathcal{C}} \mathbf{Pr}_{(x, y) \sim D} [g(x) \neq y]$
to denote the optimal misclassification error.
\end{definition}

A remark is in order about the definition. While the TCS community had only considered
the case that the upper bound $\eta$ on the Massart noise rate is {\em strictly smaller} than $1/2$,
this is not an essential assumption in the model. In fact, the original definition of the Massart model~\cite{Massart2006}
allows for $\eta = 1/2$. (Note that it is possible that $\eta = 1/2$ while $\mathrm{OPT}$ is much smaller.)

The Massart noise model is a natural semi-random input model that was formulated in~\cite{Massart2006}.
An equivalent noise model had already been defined in the 80s
by Sloan and Rivest~\cite{Sloan88, Sloan92, RivestSloan:94, Sloan96}
(under the name ``malicious misclassification noise'') and a very similar definition
had been proposed and studied even earlier by Vapnik~\cite{Vapnik82}.
The {\em sample complexity} of PAC learning halfspaces with Massart noise is well-understood.
For example, it is known (see, e.g.,~\cite{Massart2006}) that for any concept class
$\mathcal{C}$ of VC dimension $d$, $O(d/\epsilon^2)$ samples
information-theoretically suffice to compute a hypothesis with misclassification error $\mathrm{OPT}+ \epsilon$,
where  $\mathrm{OPT} = \mathbf{E}_{x \sim D_{x}} [\eta(x)]$.
This implies that halfspaces on $\mathbb{R}^m$ are learnable in the Massart model with
$O(m/\epsilon^2)$ samples.

In sharp contrast, our understanding of the {\em algorithmic aspects} of
PAC learning various natural concept classes with Massart noise
is startlingly poor and has remained a tantalizing open problem
in computational learning theory since the 1980s.
In~\cite{Sloan88} (see also~\cite{Sloan92}),
Sloan defined the malicious misclassification noise model
(an equivalent formulation of Massart noise)
and asked  whether there exists an efficient learning algorithm
for Boolean disjunctions, i.e., ORs of Boolean literals --- a very
special case of halfspaces ---  in this model.
About a decade later, Edith Cohen~\cite{Cohen:97} asked
the same question for the general class of halfspaces.
The problem remained open, even for weak learning,
and was highlighted in Avrim Blum's FOCS 2003 tutorial~\cite{Blum03}.
Surprisingly, until fairly recently, it was not even known whether
there exists an efficient algorithm that achieves misclassification error
$49\%$ for Massart halfspaces with noise rate upper bound of $\eta = 1\%$.

Recent work~\cite{DGT19} made the first algorithmic progress on this learning problem.
Specifically, \cite{DGT19} gave a $\mathrm{poly}(m, 1/\epsilon)$-time learning algorithm for Massart halfspaces
with error guarantee of $\eta+\epsilon$, where $\eta$ is the upper bound on the Massart noise rate.
This is an {\em absolute} error guarantee which cannot be improved  in general ---
since it may well be the case that $\mathrm{OPT} = \eta$ (this in particular happens when $\eta(x) = \eta$ for all $x \in X$).
Motivated by \cite{DGT19}, more recent work~\cite{DiakonikolasIKL21} gave an efficient boosting algorithm,
achieving error $\eta+\epsilon$ for any concept class, assuming the existence of a weak learner for the class.

The aforementioned error bound of $\eta+\epsilon$ can be very far from the
information-theoretically optimum error of $\mathrm{OPT}+\epsilon$. Recall that
$\mathrm{OPT} = \mathbf{E}_{x \sim D_{x}} [\eta(x)] \leq \eta$ and it could well be the case that $\mathrm{OPT} \ll \eta$.
Follow-up work by~\cite{CKMY20} showed that {\em exact} learning --- specifically,
obtaining error of $\mathrm{OPT}+o(1)$, when $\mathrm{OPT}$ is close to $1/2$ ---
requires super-polynomial time in the Statistical Query (SQ) model of~\cite{Kearns:98}.
The latter SQ lower bound is very fragile in the sense that it does not even rule out {\em any}
constant factor approximation algorithm for the problem,
i.e., a $\mathrm{poly}(m, 1/\epsilon)$-time learning algorithm with error $C \cdot \mathrm{OPT}+\epsilon$,
for a universal constant $C>1$.

The aforementioned progress notwithstanding, a very large gap remains in our understanding of the
efficient learnability of halfspaces in the presence of Massart noise. In particular,
prior to the current work, the following questions remained open.
\begin{question} \label{q:open}
Is there an efficient learning algorithm for Massart halfspaces achieving
a {\em relative} error guarantee? Specifically, if $\mathrm{OPT} \ll \eta$ is it possible to efficiently achieve
error  significantly better than $\eta$? More generally, what is the best error (as a function of $\mathrm{OPT}$ and $\eta$)
that can be achieved in polynomial time?
\end{question}

We emphasize here that, throughout this work, we focus on {\em improper learning},
where the learning algorithm is allowed to output any polynomially evaluatable
hypothesis.

\medskip

\noindent In this paper, {\em we essentially resolve the efficient PAC learnability
of Massart halfspaces in the SQ model.}
Specifically, we prove a near-optimal super-polynomial SQ lower bound for this problem,
which provides {\em strong evidence that known efficient algorithms are nearly best possible.}

Before we formally state our contributions,
we require some background on SQ algorithms.

\paragraph{Statistical Query Model}
Statistical Query (SQ) algorithms are the class of algorithms
that are only allowed to query expectations of bounded functions
of the underlying distribution rather than directly access samples.
The SQ model was introduced by Kearns~\cite{Kearns:98} in the context of supervised learning
as a natural restriction of the PAC model~\cite{val84} and has been extensively studied
in learning theory. A recent line of work~\cite{FGR+13, FeldmanPV15, FeldmanGV17, Feldman17}
generalized the SQ framework for search problems over distributions. The reader
is referred to~\cite{Feldman16b} for a survey.

One can prove unconditional lower bounds on the complexity of SQ algorithms
via a notion of {\em Statistical Query dimension}.
Such a complexity measure was introduced in~\cite{BFJ+:94}
for PAC learning of Boolean functions and has been generalized
to the unsupervised setting in~\cite{FGR+13, Feldman17}.
A lower bound on the SQ dimension of a learning problem provides an unconditional lower bound
on the complexity of any SQ algorithm for the problem.

The class of SQ algorithms is fairly broad:  a wide range of known algorithmic techniques
in machine learning are known to be implementable in the SQ model.
These include spectral techniques, moment and tensor methods,
local search (e.g., Expectation Maximization), and many others
(see, e.g.,~\cite{Chu:2006, FGR+13, FeldmanGV17}).
In the context of PAC learning classes of Boolean functions (the topic of this paper),
with the exception of learning algorithms using Gaussian elimination
(in particular for the concept class of parities, see, e.g.,~\cite{BKW:03}),
all known algorithms with non-trivial performance guarantees
are either SQ or are implementable using SQs. Finally, we acknowledge very
recent work~\cite{BBHLS20} which established a close connection
between the SQ model and low-degree polynomial tests under certain assumptions.

\subsection{Our Contributions} \label{ssec:results}

Our main result shows that any efficient (i.e., using polynomially
many queries of inverse-polynomial accuracy) SQ learning algorithm for Massart halfspaces
on $\mathbb{R}^m$ cannot obtain error better than $\Omega(\eta)$, even if the optimal error
is as small as $\mathrm{OPT} = 2^{-\log^c(m)}$, for any constant $c \in (0, 1)$. This result rules out
even very weak relative approximations to the optimal value.

In more detail, we establish the following theorem:

\begin{theorem}[Main Result] \label{thm:main-inf}
For any universal constants $c, c'$ with $0< c < 1$ and $0< c'<1-c$, the following holds.
For any sufficiently large positive integer $m$ and any $0 < \eta <1/2$,
there is no SQ algorithm that PAC learns the class of halfspaces in $\mathbb{R}^m$ with $\eta$-Massart noise
to error better than $\Omega(\eta)$ using at most $\exp(\log^{1+c}(m))$ queries of accuracy
no better than $\exp(-\log^{1+c}(m))$.
This holds even if the optimal classifier has error $\mathrm{OPT} = \exp(-\log^{c'}(m))$.
\end{theorem}

Some comments are in order. First, recall that the efficient algorithm of~\cite{DGT19}
(which can be implemented in the SQ model)
achieves error arbitrarily close to $\eta$.
Moreover, it is easy to see that the Massart learning problem is computationally easy when $\mathrm{OPT} \ll 1/m$.
As a result, the ``inapproximability gap'' of $\Omega(\eta)$ versus $2^{-\log^c(m)}$ established
by Theorem~\ref{thm:main-inf} is essentially best possible (up to the universal constant in the $\Omega(\cdot)$).
For a more detailed statement, see Theorem~\ref{thm:main-formal}.

\begin{remark} \label{rem:optimal-error-large-eta}
{\em When the Massart noise rate upper bound $\eta$ approaches $1/2$,
we can replace the lower bound of $\Omega(\eta)$ appearing in Theorem~\ref{thm:main-inf}
by the sharper lower bound of $\eta  - o_{\eta}(1)$. Here the term $o_{\eta}(1)$ goes to $0$
as $\eta$ approaches $1/2$. See Theorem~\ref{thm:main-large-eta} for the statement in this regime.}
\end{remark}

It is worth comparing Theorem~\ref{thm:main-inf} to the hardness result of Daniely~\cite{Daniely16}
for PAC learning halfspaces in the {\em agnostic} model.
Daniely's result is qualitatively similar to our Theorem~\ref{thm:main-inf} with two differences:
(1) The lower bound in~\cite{Daniely16} only applies against the (much more challenging) agnostic model.
(2) In the agnostic setting, it is hard to learn halfspaces within error significantly better than $1/2$,
rather than error $\Omega(\eta)$ in the Massart setting.
Theorem~\ref{thm:main-formal} proves an SQ lower bound for a much more benign semi-random
noise model at the cost of allowing somewhat better error in polynomial time. \new{We reiterate that
error arbitrarily close to $\eta$ is efficiently achievable for Massart noise~\cite{DGT19},
and therefore our hardness gap is nearly best possible.}

\begin{remark}\label{rem:prior-result}
{\em Theorem~\ref{thm:main-inf} strengthens a recent result by the same authors~\cite{DK20-hardness-arxiv}
which established a weaker inapproximability gap for Massart halfspaces in the SQ model.
Specifically,~\cite{DK20-hardness-arxiv} showed that no efficient SQ algorithm
can learn Massart halfspaces to accuracy $1/\mathrm{polylog}(m)$, even when $\mathrm{OPT} = 2^{-\log^c(m)}$.
The main difference between the two results, which leads to the difference in the error bounds,
lies in the construction of the one-dimensional moment-matching distributions.}
\end{remark}

\subsection{Related and Prior Work} \label{ssec:related}
We have already provided some background on the Massart noise model.
Here we summarize the most relevant literature on learning halfspaces in
related noise models.

\paragraph{Random Classification Noise}

Random Classification Noise (RCN)~\cite{AL88} is the special case of Massart
noise where each label is flipped with probability {\em exactly} $\eta <1/2$.
Halfspaces are known to be efficiently learnable {\em to optimal accuracy}
in the (distribution-independent) PAC model with RCN~\cite{BlumFKV96, BFK+:97}.
In fact, it is well-known that any SQ learning algorithm~\cite{Kearns:98} can be transformed to an
RCN noise tolerant learning algorithm --- a fact that inherently fails in the presence of Massart noise.
Roughly speaking, the ability of the Massart adversary to choose {\em whether} to flip a given label
and, if so, with what probability, makes the algorithmic problem in this model
significantly more challenging.

\paragraph{Agnostic Learning}
The agnostic model~\cite{Haussler:92, KSS:94} is the strongest noise model in the literature,
where an adversary is allowed to adversarially corrupt
an arbitrary $\mathrm{OPT}<1/2$ fraction of the labels. In the distribution-independent setting,
even {\em weak} agnostic PAC learning of halfspaces (i.e., obtaining a hypothesis with non-trivial accuracy)
is known to be intractable. A long line of work (see, e.g.,~\cite{GR:06, FGK+:06short})
has established NP-hardness of weak agnostic {\em proper} learning.
(See~\cite{Feldman15} for a survey on hardness of proper learning results.)
More recently, \cite{Daniely16} gave super-polynomial lower bounds
for {\em improper} learning, under certain average-case complexity assumptions,
and simultaneously established SQ lower bounds for the problem.
Concretely, \cite{Daniely16} showed that no polynomial-time SQ algorithm for agnostically
learning halfspaces on $\mathbb{R}^m$ can compute a hypothesis with error $1/2-1/m^c$, for some constant $c>0$,
even for instances with optimal error $\mathrm{OPT} = 2^{-\log^{1-\nu}(m)}$, for some constant $\nu \in (0, 1/2)$.

Finally, it is worth noting that learning to {\em optimal} accuracy in the agnostic model is known to be computationally
hard even in the distribution-specific PAC model, and in particular under the Gaussian distribution~\cite{KlivansK14, GGK20-agnostic-SQ, DKZ20, DKPZ21}. However, these distribution-specific hardness
results are very fragile and do not preclude efficient constant factor approximations.
In fact, efficient constant factor approximate learners are known for the Gaussian
and other well-behaved distributions (see, e.g.,~\cite{ABL17, DKS18-nasty}).

\paragraph{Prior SQ Lower Bound for Massart Halfspaces}
\cite{CKMY20} showed an SQ lower bound of $m^{\Omega(\log(1/\epsilon))}$
for learning halfspaces with Massart to error $\mathrm{OPT}+\epsilon$, when $\mathrm{OPT}$ is close to $1/2$.
Specifically,~\cite{CKMY20} observed a connection between SQ learning with Massart noise and the
{\em Correlational Statistical Query (CSQ)} model, a restriction of the SQ model
defined in~\cite{BshoutyFeldman:02} (see also~\cite{Feldman08, Feldman11}).
Given this observation, \cite{CKMY20} deduced their SQ lower bound
by applying {\em as a black-box} a previously known CSQ lower bound
by Feldman~\cite{Feldman11}. This approach is inherently limited to exact learning.
Establishing lower bounds for approximate learning requires new ideas.

\paragraph{Efficient Algorithms for Distribution-Specific Learning}
Finally, we note that $\mathrm{poly}(m, 1/\epsilon)$ time learning algorithms for homogeneous Massart
halfspaces with optimal error guarantees have been developed
when the marginal distribution on examples
is well-behaved~\cite{AwasthiBHU15, AwasthiBHZ16, ZhangLC17,
YanZ17, Zhang20, DKTZ20, DKTZ20b, DKKTZ20, DKKTZ21b}.
The hardness result obtained in this paper provides additional motivation
for such distributional assumptions. As follows from our inapproximability result,
without some niceness assumption on the distribution of examples,
obtaining even extremely weak relative approximations to the optimal error
is hard.

\paragraph{Broader Context}
This work is part of the broader direction of understanding the computational complexity of
robust high-dimensional learning in the distribution-independent setting.
A long line of work, see, e.g.,~\cite{KLS09, ABL17, DKKLMS16, LaiRV16, DKK+17, DKKLMS18-soda,
DKS18-nasty, KlivansKM18, DKS19, DKK+19-sever} and the recent survey~\cite{DK19-survey},
has given efficient robust learners for a range of high-dimensional estimation tasks (both supervised and unsupervised)
in the presence of a small constant fraction of adversarial corruptions.
These algorithmic results inherently rely on the assumption that the clean data
is drawn from a ``well-behaved'' distribution.

On the other hand, the recent work~\cite{DGT19} established that efficient robust learners with non-trivial error guarantees
are achievable {\em even in the distribution-independent setting}, under the more ``benign'' Massart model.
This result provided compelling evidence that there are realistic noise models in which efficient algorithms
are possible without imposing assumptions on the good data distribution.
Conceptually, the result of this paper shows that, even in such semi-random noise models,
there can be strong computational limitations in learnability --- in the sense that
it is computationally hard to achieve even {\em weak relative approximations} to the optimal error.

\subsection{Overview of Techniques} \label{ssec:techniques}

At a high level, our proof leverages the SQ lower bound framework developed in~\cite{DKS17-sq}.
We stress that, while this framework is a key ingredient of our construction, employing it
in our context requires new conceptual and
technical ideas, as we explain in the proceeding discussion.

Roughly speaking, the prior work \cite{DKS17-sq} established the following generic SQ-hardness result:
Let $A$ be a one-dimensional distribution that matches the first $k$ moments with the standard Gaussian $G$
\new{and satisfying the additional technical condition that its chi-squared norm with $G$ is not too large.}
Suppose we want to distinguish between the standard high-dimensional Gaussian $N(0, I)$ on $\mathbb{R}^m$ and a
distribution $\mathbf{P}^A_v$ that is a copy of $A$ in a random direction \new{$v$}
and is a standard Gaussian in the orthogonal complement.
Then any SQ algorithm for this hypothesis testing task requires super-polynomial complexity.
\new{Roughly speaking, any SQ algorithm distinguishing between the two cases requires either
at least $m^{\Omega(k)}$ samples or at least $2^{m^{\Omega(1)}}$ time.}

In the context of the current paper, we will in fact require a generalization of the latter generic result that holds
even if the one-dimensional distribution $A$ {\em nearly} matches the first $k$ moments with $G$.
Furthermore, in contrast to the unsupervised estimation problem studied in \cite{DKS17-sq},
in our context we require a generic statement establishing the SQ-hardness of a {\em binary classification} problem.
Such a statement (Proposition~\ref{prop:generic-sq}) is not hard to derive from the techniques of \cite{DKS17-sq}.

In more detail, Proposition~\ref{prop:generic-sq} shows the following:
Let $A$ and $B$ be univariate distributions (approximately) matching their first $k$ moments with $G$
(and each having not too large chi-squared \new{norm with respect to} $G$)
and let $p\in (0,1)$. We consider the distribution on labeled samples $\mathbf{P}^{A,B,p}_v$
that returns a sample from $(\mathbf{P}^A_v,1)$ with probability $p$
and a sample from $(\mathbf{P}^B_v,-1)$ with probability $1-p$.
Given labeled examples from $\mathbf{P}^{A,B,p}_v$, for an unknown direction $v$,
the goal is to output a Boolean-valued hypothesis with small misclassification error.
Note that it is straightforward to obtain error $\min\{p, 1-p \}$
(as one of the two constant functions achieves this).
We show that obtaining slightly better error is hard in the SQ model.

To leverage the aforementioned result in our circumstances,
we would like to establish the existence of a distribution $(X,Y)$ on $\mathbb{R} \times \{ \pm 1\}$
{\em that corresponds to a halfspace with Massart noise}
such that both the distribution of $X $ conditioned on $Y=1$ (denoted by $(X \mid Y=1)$)
and the distribution of $X$ conditioned on $Y=-1$ (denoted by $(X \mid Y=-1)$)
approximately match their first $k$ moments with the standard Gaussian.
{\em Note that $k$ here is a parameter that we would like to make as large as possible. In particular,
to prove a super-polynomial SQ lower bound, we need to be able to make this parameter
$k$ {\em super-constant} (as a function of the ambient dimension).}

Naturally, a number of obstacles arise while trying to achieve this.
{\em In particular, achieving the above goal directly is provably impossible} for the following reason.
Any distribution $X$ that even approximately matches a {\em constant} number
of low-order moments with the standard Gaussian will satisfy $\mathbf{E}[f(X)] \approx \mathbf{E}[f(G)]$
for any halfspace (LTF) $f$.
To see this fact, we can use the known statement (see, e.g.,~\cite{DGJ+:10})
that any halfspace $f$ can be sandwiched between low-degree polynomials
$f_+\geq f \geq f_-$ with $\mathbf{E}[f_+(G)-f_-(G)]$ small.
This structural result implies that if both conditional distributions $(X \mid Y=1)$ and $(X \mid Y=-1)$
approximately match their low-degree moments with $G$,
then $\mathbf{E}[f(X)|Y=1]$ will necessarily be close to $\mathbf{E}[f(X)|Y=-1]$,
which cannot hold in the presence of Massart noise.

In order to circumvent this obstacle, we will instead prove a super-polynomial SQ lower bound
against learning degree-$d$ polynomial threshold functions (PTFs) under the Gaussian distribution
with Massart noise, for an appropriate (super-constant) value of the degree $d$.
Since a degree-$d$ PTF on the vector random variable $X \in \mathbb{R}^m$ is equivalent
to an LTF on $X^{\otimes d}$ --- a random variable in $m^d$ dimensions ---
we will thus obtain an SQ lower bound for the original halfspace Massart learning problem.
We note that a similar idea was used in~\cite{Daniely16} to prove an SQ lower bound
for the problem of learning halfspaces in the agnostic model.

The next challenge is, of course, to construct the required moment-matching distributions in one dimension.
{\em Even for our reformulated PTF learning problem, it remains unclear whether this is even possible.}
For example, let $f(x)=\mathrm{sign}(p(x))$ be a degree-$d$ PTF.
Then it will be the case that $\mathbf{E}[p(X)Y] = \mathbf{E}[p(X)f(X)(1-2\eta(X))] = \mathbf{E}[|p(X)|(1-2\eta(X))] >0$.
This holds despite the fact that $\mathbf{E}[p(X) \mid Y=1] \approx \mathbf{E}[p(X) \mid Y=-1] \approx \mathbf{E}[p(G)]$.
If $\mathbf{E}[p(G)]>0$, it will be the case that $\mathbf{E}[p(X) \mid Y=-1]$ will be positive,
despite the fact that the conditional distribution of $X \mid Y=-1$ is almost entirely supported
on the region where $p(X) < 0$. Our construction will thus need to take advantage of finding points
where $|p(X)|$ is very large.

Fortunately for us, something of a miracle occurs here. Consider a discrete univariate Gaussian $G_{\delta}$
with spacing \new{$\sigma$} between its values. It is not hard to show that $G_{\delta}$ approximately matches moments
with the standard Gaussian $G$ to error $\exp(-\Omega(1/\new{\sigma}^2))$ (see Lemma~\ref{lem:disc-Gaussian-mm}).
On the other hand, all but a tiny fraction of the probability mass of $G_{\new{\sigma}}$ is supported
on $d=\tilde O(1/\new{\sigma})$ points.
Unfortunately, a discrete Gaussian is not quite suitable for the conditional distributions in our construction,
as its $\chi^2$ inner product with respect to the standard Gaussian is infinite.
We can fix this issue by replacing the single discrete Gaussian with an average of discrete Gaussians with different offsets.
Doing so, we obtain a distribution that nearly-matches many moments with the standard Gaussian
such that all but a small fraction of its mass is supported on a small number of intervals.

As a first attempt, we can let one of our conditional distributions be
this average of ``offset discrete Gaussians'' described above,
and the other be a similar average with different offsets. Thus, both conditional distributions nearly-match moments
with the standard Gaussian and are approximately supported on a small number of (disjoint) intervals.
This construction actually suffices to prove a lower bound for (the much more challenging) agnostic learning model.
Unfortunately however, for the Massart noise model, additional properties are needed.
In particular, for a univariate PTF with Massart noise, it must be the case that except for points $x$
in a small number of intervals, we have that $\mathbf{Pr}[Y=1 \mid X=x] > \mathbf{Pr}[Y=-1 \mid X=x]$;
whereas in the above described construction
we have to alternate infinitely many times between $Y=1$ being more likely and $Y=-1$ more likely.

To circumvent this issue, we need the following subtle modification of our construction.
Let $G_{\new{\sigma},\theta}$ be the discrete Gaussian supported on the points $n\new{\sigma}+\theta$,
for $n\in \mathbb{Z}$ (Definition~\ref{def:disc-Gauss}).
Our \new{previous (failed)} construction involved taking an average of
$G_{\new{\sigma},\theta}$, for some \emph{fixed} $\new{\sigma}$ and $\theta$ varying in some range.
Our modified construction will involve taking an average of $G_{\new{\sigma},\theta}$,
where both $\new{\sigma}$ and $\theta$ {\em vary together}. The effect of this feature will be that
instead of producing a distribution whose support is a set of evenly spaced intervals of the same size,
the support of our distributions will instead consist of a set of evenly spaced intervals
whose size grows with the distance from the origin. This means that for points $x$ near $0$,
the support will essentially be a collection of small, disjoint intervals.
But when $x$ becomes large enough, these intervals will begin to overlap,
causing all sufficiently large points $x$ to be in our support.
By changing the offsets used in defining the conditional distribution for $Y=1$
and the conditional distribution for $Y=-1$, we can ensure that for points $x$ with $|x|$ small
that the supports of the two conditional distributions remain disjoint. This in particular allows us
to take the optimal error $\mathrm{OPT}$ to be very small.
However, for larger values of $|x|$, the supports become the same.
Finally, by adjusting the prior probabilities of $Y=1$ and $Y=-1$,
we can ensure that $\mathbf{Pr}[Y=1 \mid X=x] > ((1-\eta)/(\eta)) \, \mathbf{Pr}[Y=-1 \mid X=x]$
for all points $x$ with $|x|$ sufficiently large. This suffices to show that the underlying
distribution corresponds to a Massart PTF.

\new{
\subsection{Organization} \label{ssec:structure}
The structure of this paper is as follows:
In Section~\ref{sec:prelims}, we review the necessary background on the Statistical Query model. In Section~\ref{sec:proof-cont}, we prove our SQ lower bounds for Massart halfspaces. Finally, in Section~\ref{sec:conc}, we conclude and suggest a few
directions for future work.
}

\section{Preliminaries} \label{sec:prelims}

\paragraph{Notation}
For $n \in \mathbb{Z}_+$, we denote $[n] \stackrel{{\mathrm {\footnotesize def}}}{=} \{1, \ldots, n\}$.
We will use standard notation for norms of vectors and functions,
that will be presented before it is used in subsequent sections.
We use $\mathbf{E}[X]$ for the expectation of random variable $X$ and $\mathbf{Pr}[\mathcal{E}]$
for the probability of event $\mathcal{E}$.

\paragraph{Basics on Statistical Query Algorithms.}
We will use the framework of Statistical Query (SQ) algorithms for problems over distributions
introduced in~\cite{FGR+13}.
We start by defining a decision problem over distributions.

\begin{definition}[Decision Problem over Distributions] \label{def:decision}
We denote by $\mathcal{B}(\mathcal{D}, D)$ the decision (or hypothesis testing) problem in which
the input distribution $D'$ is promised to satisfy either (a) $D' = D$ or (b) $D' \in \mathcal{D}$,
and the goal of the algorithm is to distinguish between these two cases.
\end{definition}

We define SQ algorithms as algorithms that do not have direct access to samples from the distribution,
but instead have access to an SQ oracle. We consider the following standard oracle.

\begin{definition}[$\mathrm{STAT}$ Oracle]\label{def:stat}
For a tolerance parameter $\tau >0$ and any bounded function $f: \mathbb{R}^n \to [-1, 1]$,
$\mathrm{STAT}(\tau)$ returns a value $v \in \left[\mathbf{E}_{x \sim D} [f(x)] - \tau,  \mathbf{E}_{x \sim D} [f(x)] + \tau \right]$.
\end{definition}

We note that \cite{FGR+13} introduced another related oracle,
which is polynomially equivalent to $\mathrm{STAT}$.
Since we prove super-polynomial lower bounds here, there is no essential distinction between these oracles.
To define the SQ dimension, we need
the following definitions.

\begin{definition}[Pairwise Correlation] \label{def:pc}
The pairwise correlation of two distributions with probability density functions
$D_1, D_2 : \mathbb{R}^m \to \mathbb{R}_+$ with respect to a distribution with density $D: \mathbb{R}^m \to \mathbb{R}_+$,
where the support of $D$ contains the supports of $D_1$ and $D_2$,
is defined as $\chi_{D}(D_1, D_2) \stackrel{{\mathrm {\footnotesize def}}}{=} \int_{\mathbb{R}^m} D_1(x) D_2(x)/D(x) dx -1$.
\end{definition}

We remark that when $D_1=D_2$ in the above definition,
the pairwise correlation is identified with the $\chi^2$-divergence between $D_1$ and $D$,
i.e.,  $\chi^2(D_1, D) \stackrel{{\mathrm {\footnotesize def}}}{=} \int_{\mathbb{R}^m} D_1(x)^2/D(x) dx -1$.

\begin{definition} \label{def:uncor}
We say that a set of $s$ distributions $\mathcal{D} = \{D_1, \ldots , D_s \}$ over $\mathbb{R}^m$
is $(\gamma, \beta)$-correlated relative to a distribution $D$ if
$|\chi_D(D_i, D_j)| \leq \gamma$ for all $i \neq j$, and $|\chi_D(D_i, D_j)| \leq \beta$ for $i=j$.
\end{definition}

We are now ready to define our notion of dimension.

\begin{definition}[Statistical Query Dimension] \label{def:sq-dim}
For $\beta, \gamma > 0$, a decision problem $\mathcal{B}(\mathcal{D}, D)$,
where $D$ is a fixed distribution and $\mathcal{D}$ is a family of distributions over $\mathbb{R}^m$,
let $s$ be the maximum integer such that there exists a finite set of distributions
$\mathcal{D}_D \subseteq \mathcal{D}$
such that $\mathcal{D}_D$ is $(\gamma, \beta)$-correlated relative to $D$ and $|\mathcal{D}_D| \geq s.$
We define the {\em Statistical Query dimension} with pairwise correlations $(\gamma, \beta)$
of $\mathcal{B}$ to be $s$ and denote it by $\mathrm{SD}(\mathcal{B},\gamma,\beta)$.
\end{definition}

Our proof bounds below the Statistical Query dimension
of the considered learning problem. This implies lower bounds on
the complexity of any SQ algorithm for the problem using the following standard result.

\begin{lemma}[Corollary 3.12 in~\cite{FGR+13}] \label{lem:sq-from-pairwise}
Let $\mathcal{B}(\mathcal{D}, D)$ be a decision problem, where $D$ is the reference distribution
and $\mathcal{D}$ is a class of distributions. For $\gamma, \beta >0$,
let $s= \mathrm{SD}(\mathcal{B}, \gamma, \beta)$. For any $\gamma' > 0,$ any
SQ algorithm for $\mathcal{B}$ requires at least $s \cdot \gamma' /(\beta - \gamma)$ queries to the
$\mathrm{STAT}(\sqrt{\gamma + \gamma'})$ oracle.
\end{lemma}

\section{SQ Hardness of Learning Halfspaces with Massart Noise} \label{sec:proof-cont}
In this section, we prove our SQ lower bounds for Massart halfspaces,
establishing Theorem~\ref{thm:main-inf}. In more detail, we establish the following
result, which implies Theorem~\ref{thm:main-inf}.

\begin{theorem}[SQ Hardness of Learning Massart Halfspaces on $\mathbb{R}^M$] \label{thm:main-formal}
Let $\mathrm{OPT}>0$ and $M \in \mathbb{Z}_+$ be such that
$\log(M)/(\log\log(M))^3$ is at least a sufficiently large constant multiple of $\log(1/\mathrm{OPT})$.
There exists a parameter $\tau \stackrel{{\mathrm {\footnotesize def}}}{=} M^{-\Omega\left( \frac{\log(M)}{{\log\log(M)}^3}/\log(1/\mathrm{OPT}) \right)}$
such that no SQ algorithm can learn the class of halfspaces on $\mathbb{R}^M$
in the presence of $\eta$-Massart noise, where $\mathrm{OPT}< \eta <1/2$, within
error better than $\Omega(\eta)$ using at most $1/\tau$ queries
of tolerance $\tau$.
This holds even if the optimal binary classifier has misclassification error at most $\mathrm{OPT}$.
\end{theorem}

\new{As an immediate corollary of Theorem~\ref{thm:main-formal},
by taking $\mathrm{OPT} = \exp(- \log^{c'}(M))$ for any fixed
constant $c' \in (0, 1)$, we obtain a super-polynomial SQ lower bound
against learning a hypothesis with error better than $\Omega(\eta)$,
even when error $\mathrm{OPT}$ is possible. Specifically, this setting of parameters immediately implies
Theorem~\ref{thm:main-inf}, since
$\frac{\log(M)}{{\log\log(M)}^3}\new{/}\log(1/\mathrm{OPT}) = \frac{\log^{1-c'}(M)}{{\log\log(M)}^3} > \log^{c}(M)$,
where $0< c < 1-c'$, and therefore $1/\tau  \gg \exp(\log^{1+c}(M))$.

\begin{remark}\label{rem:sharp-error}
{\em In addition to Theorem~\ref{thm:main-formal}, we establish
an alternative ``inapproximability gap'' of $1/2- O(\sqrt{1/2-\eta})$ versus
$\exp(- \log^{c'}(M))$, which implies a sharper error lower bound when $\eta$ approaches $1/2$.
Specifically, for $\eta$ close to $1/2$, we obtain an error lower bound of $\eta - o_{\eta}(1)$, even
if $\mathrm{OPT} = \exp(- \log^{c'}(M))$. See Theorem~\ref{thm:main-large-eta} for the formal statement.}
\end{remark}

}

\paragraph{Structure of This Section}
The structure of this section is as follows:
In Section~\ref{ssec:high-dim}, we review the SQ framework of~\cite{DKS17-sq}
with the necessary enhancements and modifications required for our supervised setting.
In Section~\ref{ssec:one-dim}, we establish the existence of the one-dimensional distributions
with the desired approximate moment-matching properties.
In Section~\ref{ssec:combine}, we put everything together
to complete the proof of Theorem~\ref{thm:main-formal}.
In Section~\ref{ssec:large-eta}, we establish our shaper lower bounds for $\eta$ close to $1/2$,
proving Theorem~\ref{thm:main-large-eta}.

\subsection{Generic SQ Lower Bound Construction} \label{ssec:high-dim}

We start with the following definition:

\begin{definition} [High-Dimensional Hidden Direction Distribution] \label{def:pv-hidden}
{For a distribution $A$ on the real line with probability density function $A(x)$ and}
 a unit vector $v \in \mathbb{R}^m$, consider the distribution over $\mathbb{R}^m$ with probability density function
$\mathbf{P}^A_v(x) = A(v \cdot x) \exp\left(-\|x - (v \cdot x) v\|_2^2/2\right)/(2\pi)^{(m-1)/2}.$
That is, $\mathbf{P}^A_v$ is the product distribution whose orthogonal projection onto the direction of $v$ is $A$,
and onto the subspace perpendicular to $v$ is the standard $(m-1)$-dimensional normal distribution.
\end{definition}

We consider the following condition:

\begin{cond} \label{cond:moments}
Let $k \in \mathbb{Z}_+$ and $\nu>0$.
The distribution $A$ is such that (i) the first $k$ moments of $A$
agree with the first $k$ moments of $N(0,1)$ up to error at most $\nu$, and (ii) $\chi^2(A,N(0,1))$ is finite.
\end{cond}

Note that Condition~\ref{cond:moments}-(ii) above
implies that the distribution $A$ has a pdf, which we will denote by $A(x)$.
We will henceforth blur the distinction between a distribution and its pdf.

Our main result in this subsection makes essential use of the following key lemma:

\begin{lemma}[Correlation Lemma] \label{lem:cor}
Let $k \in \mathbb{Z}_+$.
If the univariate distribution $A$ satisfies Condition \ref{cond:moments},
then for all $v,v' \in \mathbb{R}^m$, with $|v\cdot v'|$ less than a sufficiently small constant, we have that
\begin{equation} \label{eqn:corr-pv}
|\chi_{N(0,I)}(\mathbf{P}^A_v, \mathbf{P}^A_{v'})| \leq |v \cdot v'|^{k+1} \chi^2(A, N(0,1)) + \nu^2 \;.
\end{equation}
\end{lemma}
This lemma is a technical generalization of Lemma~3.4 from~\cite{DKS17-sq},
which applied under {\em exact} moment matching assumptions. The proof is deferred to Appendix~\ref{app:cor}.

We will also use the following standard fact:

\begin{fact}\label{fact:near-orth-vec}
For any constant $c>0$ there exists a set $S$ of $2^{\Omega_c(m)}$ unit vectors in $\mathbb{R}^m$
such that any pair $u, v \in S$, with $u \neq v$, satisfies $|u\cdot v|<c$.
\end{fact}

In fact, an {appropriate size} set of random unit vectors
satisfies the above statement {with high probability}.
We note that \cite{DKS17-sq} made use of a similar statement, albeit with different parameters.

We will establish an SQ lower bound for the following binary classification problem.

\begin{definition}[Hidden Direction Binary Classification Problem] \label{def:class}
Let $A$ and $B$ be distributions on $\mathbb{R}$ satisfying Condition \ref{cond:moments} with
parameters $k \in \mathbb{Z}_+$ and $\nu \in \mathbb{R}_+$, and let $p\in (0,1)$. For $m \in \mathbb{Z}_+$ and a unit vector $v\in \mathbb{R}^m$,
define the distribution $\mathbf{P}^{A,B,p}_v$ on $\mathbb{R}^m\times \{\pm 1\}$ that returns a sample
from $(\mathbf{P}^A_v,1)$ with probability $p$ and a sample from $(\mathbf{P}^B_v,-1)$ with probability $1-p$.
The corresponding binary classification problem is the following: Given access to a distribution on labeled
examples of the form $\mathbf{P}^{A,B,p}_v$, for a fixed but unknown unit vector $v$,
output a hypothesis $h: \mathbb{R}^m \to \{\pm1\}$ such that $\mathbf{Pr}_{(X,Y) \sim \mathbf{P}^{A,B,p}_v}[h(X)\neq Y]$
is (approximately) minimized.
\end{definition}

Note that it is straightforward to obtain misclassification error $\min\{p, 1-p \}$
(as one of the identically constant functions achieves this guarantee).
We show that obtaining slightly better error is hard in the SQ model.
The following result is the basis for our SQ lower bounds:

\begin{proposition}[Generic SQ Lower Bound] \label{prop:generic-sq}
{Consider the classification problem of Definition~\ref{def:class}.}
Let $\tau \stackrel{{\mathrm {\footnotesize def}}}{=} \nu^2 + 2^{-k}(\chi^2(A, N(0,1))+\chi^2(B, N(0,1)))$.
Then any SQ algorithm that, {given access to a distribution $\mathbf{P}^{A,B,p}_v$ for an unknown
$v \in \mathbb{R}^m$,} outputs a hypothesis $h: \mathbb{R}^m \to \{\pm1\}$ such that
$\mathbf{Pr}_{(X,Y) \sim \mathbf{P}^{A,B,p}_v}[h(X)\neq Y] < \min(p,1-p)- \new{4} \sqrt{\tau}$ must either make queries
of accuracy better than $2\sqrt{\tau}$ or must make at least
$2^{\Omega(m)}\tau/(\chi^2(A, N(0,1))+\chi^2(B, N(0,1)))$ statistical queries.
\end{proposition}

\begin{proof}[Proof of Proposition~\ref{prop:generic-sq}]
The proof proceeds as follows: We start by defining a related hypothesis testing problem $\mathcal{H}$
and show that $\mathcal{H}$ efficiently reduces to our learning (search) problem. We then leverage the machinery
of this section (specifically, Lemma~\ref{lem:cor} and Fact~\ref{fact:near-orth-vec}) to prove an SQ lower bound
for $\mathcal{H}$, which in turns implies an SQ lower bound for our learning task.

Let $S$ be a set of $2^{\Omega(m)}$ unit vectors in $\mathbb{R}^m$ whose pairwise inner products are
at most a sufficiently small universal constant $c$. {(In fact, any constant $c<1/2$ suffices.)}
By Fact~\ref{fact:near-orth-vec}, such a set is guaranteed to exist.
Given $S$, our hypothesis testing problem is defined as follows.

\begin{definition}[Hidden Direction Hypothesis Testing Problem] \label{def:hyp-test}
In the context of Definition~\ref{def:class}, the testing problem $\mathcal{H}$
is the task of distinguishing between: (i) the distribution $\mathbf{P}^{A,B,p}_v$, for $v$ randomly chosen from $S$,
and (ii) the distribution $G'$ on $\mathbb{R}^m \times \{ \pm 1\}$, where for $(X, Y) \sim G'$ we have that
$X$ is a standard Gaussian {$G \sim N(0, I)$},
and $Y$ is independently $1$ with probability $p$ and $-1$ with probability $1-p$.
\end{definition}

We claim that $\mathcal{H}$ efficiently reduces to our learning task. In more detail,
any SQ algorithm that computes a hypothesis $h$ satisfying
$\mathbf{Pr}_{(X,Y) \sim \mathbf{P}^{A,B,p}_v}[h(X)\neq Y] < \min(p,1-p)-\new{4} \sqrt{\tau}$ can be used as a black-box
to distinguish between $\mathbf{P}^{A,B,p}_v$, for $v$ randomly chosen from $S$, and $G'$.
Indeed, suppose we have such a hypothesis $h$.
Then, with one additional {query} to estimate the $\mathbf{Pr}[h(X)\neq Y]$,
we can distinguish between $\mathbf{P}^{A,B,p}_v$, for $v$ randomly chosen from $S$,
and $G'$ for the following reason: For any function $h$, we have that
$\mathbf{Pr}_{(X,Y)\sim G'}[h(X)\neq Y] \geq \min(p,1-p)$.

It remains to prove that solving the hypothesis testing problem $\mathcal{H}$
is impossible for an SQ algorithm with the desired parameters.
We will show this using {Lemma~\ref{lem:sq-from-pairwise}}.

More specifically, we need to show that for $u , v \in S$ we have
that $|\chi_{G'}(\mathbf{P}^{A,B,p}_v,\mathbf{P}^{A,B,p}_u)|$ is small.
Since $G',\mathbf{P}^{A,B,p}_v,$ and $\mathbf{P}^{A,B,p}_u$ all assign $Y=1$ with probability $p$,
it is not hard to see that
\begin{align*}
\chi_{G'}(\mathbf{P}^{A,B,p}_v,\mathbf{P}^{A,B,p}_u)
= & \; p \; \chi_{(G' \mid Y=1)}\left( (\mathbf{P}^{A,B,p}_v \mid Y=1) , (\mathbf{P}^{A,B,p}_u \mid Y=1) \right) + \\
& (1-p) \; \chi_{(G' \mid Y=-1)} \left( (\mathbf{P}^{A,B,p}_v \mid Y=-1) , (\mathbf{P}^{A,B,p}_u \mid Y=-1) \right)\\
 = & \; p \; \chi_{G}(\mathbf{P}^A_v , \mathbf{P}^A_u) + (1-p) \; \chi_{G}(\mathbf{P}^B_v, \mathbf{P}^B_u) \;.
\end{align*}
By Lemma \ref{lem:cor}, it follows that
$$\chi_{G'}(\mathbf{P}^{A,B,p}_v,\mathbf{P}^{A,B,p}_u) \leq \nu^2 + 2^{-k}(\chi^2(A, N(0,1))+\chi^2(B, N(0,1)))=\tau \;.$$
A similar computation shows that
$$\chi_{G'}(\mathbf{P}^{A,B,p}_v,\mathbf{P}^{A,B,p}_v) = \chi^2(\mathbf{P}^{A,B,p}_v,G')\leq \chi^2(A, N(0,1))+\chi^2(B, N(0,1)) \;.$$
An application of Lemma~\ref{lem:sq-from-pairwise} for $\gamma = \gamma' = \tau$ and
$\beta = \chi^2(A, N(0,1))+\chi^2(B, N(0,1))$ completes the proof.
\end{proof}

\subsection{Construction of Univariate Moment-Matching Distributions} \label{ssec:one-dim}
\new{In this subsection, we give our univariate approximate moment-matching construction (Proposition~\ref{mainProp}),
which is the key new ingredient to establish our desired SQ lower bound.
The moment-matching construction of this subsection
(along with its refinement for $\eta$ close to $1/2$ presented
in Section~\ref{ssec:large-eta}) is the main technical contribution of this work.}

\paragraph{Additional Notation}
We will be working with moments of distributions
that are best described as normalizations of (unnormalized positive) measures.
For notational convenience, by slight abuse of notation,
we define $\mathbf{E}[X]$, for any non-negative measure on $\mathbb{R}$, by $\mathbf{E}[X] = \int tdX(t).$
Note that this is equivalent to $\mathbf{E}[X] = \|X\|_1 \mathbf{E}[Y]$, where $Y=X/\|X\|_1$
is the normalized version of $X$.
Furthermore, we denote the $k^{th}$ moment of such an $X$ by $\mathbf{E}[X^k]$.

We write $E \gg F$ for two expressions $E$ and $F$ to denote that $E \geq c \, F$, where $c>0$
is a sufficiently large universal constant (independent of the variables or parameters on which $E$ and $F$ depend).
Similarly, we write $E \ll F$ to denote that $E \leq c \, F$, where $c>0$
is a sufficiently small universal constant.

We will use $G$ for the measure of the univariate standard Gaussian distribution $N(0, 1)$
and $g(x) = \frac{1}{\sqrt{2\pi}} \exp(-x^2/2)$ for its probability density function.

\medskip

We view the real line as a measurable space endowed with the $\sigma$-algebra
of Lebesgue measurable sets. We will construct two (non-negative, finite) measures $\mathcal{D}_{+}$ and $\mathcal{D}_{-}$
on this space with appropriate properties.
The main technical result of this section is captured in the following proposition.

\begin{proposition}\label{mainProp}
Let $0< \epsilon < s <1$ be real numbers such that $s/\epsilon$ is at least a sufficiently large universal constant.
Let \new{$0< \eta < 1/2$}.
There exist measures $\mathcal{D}_{+}$ and $\mathcal{D}_{-}$ over $\mathbb{R}$ and a union $J$
of $d = O(s/\epsilon)$ intervals on $\mathbb{R}$ such that:
\begin{enumerate}
\item \label{prop:1} (a) $\mathcal{D}_{+}=0$ on $J$, and (b) $\mathcal{D}_{+} / \mathcal{D}_{-} > (1-\eta)/\eta$ on $J^c := \mathbb{R} \setminus J$.
\item \label{prop:2} All but $\zeta = O(\eta s/\epsilon)\exp(-\Omega(s^4/\epsilon^2))$ of the measure of $\mathcal{D}_{-}$ lies in $J$.
\item \label{prop:3} For any $t \in \mathbb{N}$, the distributions $\mathcal{D}_{+}/\|\mathcal{D}_{+}\|_1$ and $\mathcal{D}_{-}/\|\mathcal{D}_{-}\|_1$ have their
first $t$ moments matching those of $G$ within additive error at most ${(t+1)!} \exp(-\Omega(1/s^2))$.
\item \label{prop:4} (a) $\mathcal{D}_{+}$ is at most $O(s/\epsilon) \; G$, and
(b) $\mathcal{D}_{-}$ is at most $O(s\eta /\epsilon) \; G$.
\item \label{prop:5} {(a)} $\|\mathcal{D}_+\|_1 = \Theta(1)$, {and (b) $\|\mathcal{D}_-\|_1 = \Theta(\eta)$}.
\end{enumerate}
\end{proposition}

\paragraph{Discussion}
Essentially, in our final construction, $\mathcal{D}_{+}$ will be proportional to the distribution
of $X$ conditioned on $Y=1$ and $\mathcal{D}_{-}$ proportional to the distribution of $X$ conditioned on $Y=-1$.
Furthermore, the ratio of the probability of $Y=1$ to the probability of $Y=-1$ will be equal to $\|\mathcal{D}_{+}\|_1/ \|\mathcal{D}_{-}\|_1$.
\new{The Massart PTF that $f(X)$ is supposed to simulate will be $-1$ on $X \in J$ and $1$ elsewhere
(thus making it a degree-$2d$ PTF).}

We now provide an explanation of the properties established in Proposition~\ref{mainProp}.
Property \ref{prop:1}(a) says that $Y$ will deterministically be $-1$ on $J$, while property
\ref{prop:1}(b) says that the ratio between $\mathcal{D}_{+}$ and $\mathcal{D}_{-}$ will be greater than
$(1-\eta)/\eta$ on the complement of $J$. \new{This implies that $Y$ amounts to $f(X)$
with Massart noise at most $\eta$.}

Property \ref{prop:2} implies that $Y$ only disagrees with the target PTF with probability roughly $\zeta$,
i.e., that the optimal misclassification value $\mathrm{OPT}$ will be less than $\zeta$.

Property \ref{prop:3} says that $\mathcal{D}_{+}$ and $\mathcal{D}_{-}$, after rescaling, approximately match
many moments with the standard Gaussian, which will be necessary in establishing our SQ lower bounds.

\new{
Property \ref{prop:4}  is necessary to show that $\mathcal{D}_{+}$ and $\mathcal{D}_{-}$
have relatively small chi-squared norms.
Finally, Property\ref{prop:5} is necessary to  figure out how big the parameter $p$ (i.e., $\Pr[Y=1]$)
should be (approximately).
}

\medskip

The rest of this subsection is devoted to the proof of Proposition~\ref{mainProp}.

\begin{proof}[Proof of Proposition~\ref{mainProp}]
The proof will make essential use of the following two-parameter family of discrete Gaussians.

\begin{definition}[Discrete Gaussian] \label{def:disc-Gauss}
For $\sigma \in \mathbb{R}_+$ and $\theta \in \mathbb{R}$, let $G_{\sigma,\theta}$
denote the measure of the ``$\sigma$-spaced discrete Gaussian distribution''.
In particular,  for each $n\in \mathbb{Z}$, $G_{\sigma,\theta}$ assigns mass $\sigma g(n\sigma+\theta)$ to the point $n \sigma+\theta$.
\end{definition}

Note that $G_{\sigma,\theta}$ is not a probability measure as its total measure is not equal to one.
However, it is not difficult to show (see Lemma~\ref{lem:disc-Gaussian-mm} below)
that the measure of $G_{\sigma,\theta}$ is close to one for small $\sigma>0$,
hence can be intuitively thought of as a probability distribution.

The following lemma shows that the moments of $G_{\sigma,\theta}$
approximately match the moments of the standard Gaussian measure $G$.

\begin{lemma}\label{lem:disc-Gaussian-mm}
For all $t \in \mathbb{N}, \sigma \geq 0$, and all $\theta\in \mathbb{R}$ we have that
$\left| \mathbf{E}[G_{\sigma,\theta}^t] - \mathbf{E}[G^t] \right| = t! \, O(\sigma)^t \, \exp(-\Omega(1/\sigma^2))$.
\end{lemma}

The proof of Lemma~\ref{lem:disc-Gaussian-mm} proceeds by analyzing
the Fourier transform of $G_{\sigma,\theta}$ and using the fact that the $t^{th}$ moment
of a measure is proportional to the $t^{th}$ derivative of its Fourier transform at $0$.
The proof is deferred to Appendix~\ref{app:disc-Gaussian}.

Note that Lemma~\ref{lem:disc-Gaussian-mm} for $t=0$ implies
the total measure of $G_{\sigma,\theta}$ is $\exp(-\Omega(1/\sigma^2))$ close to one,
i.e., for small $\sigma>0$ $G_{\sigma,\theta}$ can be thought of as a probability distribution.

\paragraph{Definition of the Measures $\mathcal{D}_+$ and $\mathcal{D}_-$}

We define our measures as mixtures of discrete Gaussian distributions.
This will allow us to guarantee that they nearly match moments with the standard Gaussian.
In particular, for a  sufficiently large constant $C>0$, we define:
\begin{equation} \label{eq:d-plus}
\mathcal{D}_+ := C \, (s/\epsilon) \, \int_{0}^{\epsilon} \frac{1}{s+y} \, G_{s+y,y/2} \, dy \;,
\end{equation}
and
\begin{equation} \label{eq:d-minus}
\mathcal{D}_- := \eta \, (s/\epsilon) \, \int_{0}^{\epsilon} \frac{1}{s+y} \, G_{s+y,(y+s)/2} dy \;.
\end{equation}

We will require the following explicit formulas for $\mathcal{D}_+$ and $\mathcal{D}_{-}$,
which will be useful both in the formal proof and for the sake of the intuition.

\begin{lemma} \label{lem:formulas-d}
For all $x \in \mathbb{R}$, we have that:
\begin{equation} \label{eq:d-plus-exp}
\mathcal{D}_{+} (x)  = C \, g(x) \, (s/\epsilon) \, \sum_{n\in \mathbb{Z}}\frac{\mathbf{1}\{ x \in [ns,ns+(n+1/2)\epsilon]\}}{|n+1/2|} \;,
\end{equation}
where by $\mathbf{1}\{ x \in [ns,ns+(n+1/2)\epsilon]\}$ we denote the indicator function of the event that $x$
is between $ns$ and $ns+(n+1/2)\epsilon$, even in the case where $n<0$ and $ns+(n+1/2)\epsilon < ns$.

Similarly, we have that
\begin{equation} \label{eq:d-minus-exp}
\mathcal{D}_{-} (x)  = \eta \, g(x) \,  (s/\epsilon) \, \sum_{n\in \mathbb{Z}}\frac{\mathbf{1}\{ x \in [(n+1/2)s,(n+1/2)s+(n+1/2)\epsilon]\}}{|n+1/2|} \;.
\end{equation}
\end{lemma}

\begin{proof}
To prove the lemma, we unravel the definition of the discrete Gaussian to find that:
\begin{align*}
\mathcal{D}_+(x) & = Cs/\epsilon \int_{0}^\epsilon \frac{\sum_{n\in \mathbb{Z}} (s+y)g(n(s+y)+y/2)\delta(x-(n(s+y)+y/2)) }{s+y} dy\\
& = Cs/\epsilon \sum_{n\in \mathbb{Z}}\int_{0}^\epsilon g(n(s+y)+y/2)\delta(x-(n(s+y)+y/2))  dy\\
& = Cs/\epsilon \sum_{n\in \mathbb{Z}}\int_{0}^\epsilon g((n+1/2)y+ns)\delta(x-((n+1/2)y+ns))  dy\\
& = Cg(x)s/\epsilon \sum_{n\in \mathbb{Z}}\frac{\mathbf{1}\{ x \in [ns,ns+(n+1/2)\epsilon]\}}{|n+1/2|} \;.
\end{align*}
The calculation for $\mathcal{D}_-(x)$ is similar.
\end{proof}

\paragraph{Intuition on Definition of $\mathcal{D}_+$ and $\mathcal{D}_-$}
We now attempt to provide some intuition regarding the definition
of the above measures. We start by noting that each of $\mathcal{D}_{+} (x)$ and $\mathcal{D}_{-} (x)$
will have size roughly $g(x)$ on its support. This can be seen to imply
on the one hand that the chi-squared divergence of (the normalization of)
$\mathcal{D}_\pm$ from the standard Gaussian $G$ is not too large,
and on the other hand that $\mathcal{D}_{\pm}$
roughly satisfy Gaussian concentration bounds.

The critical information to consider is the support of these distributions.
Each of the two measures is supported on a union of intervals.
Specifically, $\mathcal{D}_+$ is supported on intervals located at the point $n \, s$ of width $|n+1/2|\epsilon$;
and $\mathcal{D}_-$ is supported on intervals located at the point $(n+1/2)s$ of width $|n+1/2|\epsilon$.
In the case where $\epsilon \ll s$, these intervals will be disjoint for small values of $n$
(roughly, for $\new{|n|} \ll s/\epsilon$).
The factor of $C>0$ difference in the definitions of the two measures
will ensure that $\mathcal{D}_+ > \mathcal{D}_- (1-\eta)/\eta$ on their joint support;
and once $|n|$ has exceeded a sufficiently large constant multiple of $s/\epsilon$,
the intervals will be wide enough that they overlap causing the support to be everything.

In other words, for $|x|$ less than a sufficiently small constant multiple of $s^2/\epsilon$,
$\mathcal{D}_+$ and $\mathcal{D}_-$ will be supported on $O(s/\epsilon)$ many intervals and will have disjoint supports.
We define $J$ to be the union of the $O(s/\epsilon)$ many intervals in the support of $\mathcal{D}_{-}$
that are not in the support of $\mathcal{D}_{+}$. With this definition, we will have that
(1) $\mathcal{D}_+$ is equal to zero in $J$, and (2) $\mathcal{D}_+/\mathcal{D}_-$ is sufficiently large on $J^c$.
Furthermore, since $\mathcal{D}_{-}$ only assigns mass to $J^c$ for $x$ with $|x| \gg s^2/\epsilon$,
we can take $\zeta = \exp(-\Omega(s^4/\epsilon^2))$.

\medskip

Given the above intuition, we begin the formal proof,
starting with moment-matching.

\begin{lemma}\label{DMomentsLem}
For $t \in \mathbb{N}$, the distributions $\mathcal{D}_+ / \|\mathcal{D}_+\|_1$ and $\mathcal{D}_-/\|\mathcal{D}_-\|_1$
match the first $t$ moments with the standard Gaussian
$G$ to within additive error $t! \, O(s)^t \, \exp(-1/s^2)$.
\end{lemma}
\begin{proof}
This follows from Lemma \ref{lem:disc-Gaussian-mm} by noting that
both of these distributions are mixtures of discrete Gaussians with $\sigma = \Theta(s)$.
\end{proof}

Our next lemma provides approximations to the corresponding $L_1$ norms.

\begin{lemma}\label{DL1Lem}
We have that
$\|\mathcal{D}_+\|_1 = \Theta(1)$ and $\|D_-\|_1 = \Theta(\eta)$.
\end{lemma}
\begin{proof}
Applying Lemma \ref{lem:disc-Gaussian-mm} with $t=0$, we get that $\|G_{s+y,y/2}\|_1 = \Theta(1)$.
Thus, working from the definition, we find that
\begin{align*}
\|\mathcal{D}_+\|_1 & = C \, (s/\epsilon) \, \int_0^{\epsilon} \frac{\Theta(1)}{s+y} dy\\
& = C \, (s/\epsilon) \, \int_0^{\epsilon} \Theta(1/s) dy\\
& = \Theta(1) \;.
\end{align*}
The proof for $\mathcal{D}_-$ follows similarly.
\end{proof}

For the rest of the proof, it will be important to analyze
the intervals on which $\mathcal{D}_{+}$ and $\mathcal{D}_{-}$ are supported.
To this end, we start by introducing the following notation.

\begin{definition}\label{def:I-n-plus-minus}
For $m\in \mathbb{Z}$, let $I_{+}^m$ be the interval with endpoints $ms$ and $ms+(m+1/2)\epsilon$,
and let $I_{-}^m$ be the interval with endpoints $(m+1/2)s$ and $(m+1/2)s+(m+1/2)\epsilon$.
Additionally, for $x \in \mathbb{R}$, let $n_{+}(x)$ be the number of integers $m$ such that $x\in I_{+}^m$,
and $n_{-}(x)$ be the number of integers $m$ such that $x\in I_{-}^m$.
\end{definition}

The following corollary is an easy consequence of the definition.

\begin{corollary}\label{mSizeCor}
For $x \in \mathbb{R}$, we have that $x\in I_{+}^m$ only if $m=x/s + O((|x|+s)\epsilon/s)$.
Similarly, $x\in I_{-}^m$ only if $m=x/s - 1/2 + O((|x|+s)\epsilon/s)$.
\end{corollary}

Combining Corollary~\ref{mSizeCor} with the explicit formulas for $\mathcal{D}_+$ and $\mathcal{D}_-$
given in Lemma~\ref{lem:formulas-d},
we have that:
\begin{corollary}\label{DSizeCor}
For all $x \in \mathbb{R}$ we have that
$$
\mathcal{D}_+(x) = \Theta(C g(x) (s^2/\epsilon) n_+(x)/(|x|+s) ) \;,
$$
and
$$
\mathcal{D}_-(x) = \Theta(\eta g(x) (s^2/\epsilon) n_-(x)/(|x|+s) ) \;.
$$
\end{corollary}
\begin{proof}
This follows from the explicit formulas for $\mathcal{D}_+$ and $\mathcal{D}_-$ given in Lemma~\ref{lem:formulas-d}
along with Corollary \ref{mSizeCor}, which implies that the denominators $|n+1/2|$ are $\Theta((|x|+s)/s)$.
\end{proof}

We next need to approximate the size of $n_+(x)$ and $n_-(x)$.
We have the following lemma.

\begin{lemma}\label{nSizeLem}
For all $x \in \mathbb{R}$, we have that
$$n_{+}(x), n_{-}(x) = |x| \left( 1/s-1/(s+\epsilon) \right)+O(1) = |x| \, \Theta(\epsilon/s^2)+O(1) \;.$$
\end{lemma}
\begin{proof}
We will prove the desired statement for $x\geq 0$ and $n_+(x)$.
The other cases follow symmetrically.
Note that $x\in I_{+}^m$ only for non-negative $m$.
For such $m$, $x\in I_{+}^m$ if and only if $ms \leq x \leq m(s+\epsilon)+\epsilon/2$.
This is the difference in the number of $m$'s for which $ms \leq x$ and
the number of $m$'s for which $m(s+\epsilon)+\epsilon/2 < x$.
The former is $|x|/s+O(1)$ and the latter is $|x|/(s+\epsilon)+O(1)$.
The lemma follows.
\end{proof}

Lemma~\ref{nSizeLem} implies the following.

\begin{corollary}\label{JSupportCor}
We have that $n_+(x) \geq 1$ for all $x$ larger than a sufficiently large constant multiple of $s^2/\epsilon$.
\end{corollary}

Combining Lemma \ref{nSizeLem} with Corollary \ref{DSizeCor}, we get the following.

\begin{corollary}\label{DBoundCor}
For all $x \in \mathbb{R}$, we have that
$$
\mathcal{D}_+(x) = O \left( g(x) (s/\epsilon) \right), \ \ \ \mathcal{D}_{-}(x) = O \left(g(x) \, \eta \, (s/\epsilon) \right) \;.
$$
\end{corollary}

A combination of Lemma \ref{nSizeLem} with Corollary \ref{DSizeCor}
also implies that on the support of $\mathcal{D}_+$ the ratio $\mathcal{D}_+/\mathcal{D}_-$ is sufficiently large.

\begin{corollary}\label{DRatioCor}
If $x \in \mathbb{R}$ is such that $\mathcal{D}_+(x) > 0$, then $\mathcal{D}_+(x)/\mathcal{D}_-(x) > (1-\eta)/\eta.$
\end{corollary}
\begin{proof}
If $\mathcal{D}_+(x)>0$, then $n_+(x) > 0$. Lemma \ref{nSizeLem} implies that $n_-(x) = n_+(x)+O(1)$,
and therefore $n_-(x)/n_+(x) = O(1)$. Combining this with Corollary \ref{DSizeCor}, we have that
$$
\mathcal{D}_+(x) / \mathcal{D}_-(x)  = \new{\Omega} (C/\eta) \;.
$$
For $C$ a sufficiently large universal constant, this implies our result.
\end{proof}

We also need to show that the intersection of the supports of $\mathcal{D}_{+}$ and $\mathcal{D}_{-}$
occurs only for $|x|$ sufficiently large. Specifically, we have the following lemma.

\begin{lemma}\label{supportIntersectLem}
For $x \in \mathbb{R}$, it holds that
$\min(n_+(x),n_-(x))>0$ only if $|x| = \Omega(s^2/\epsilon)$.
\end{lemma}
\begin{proof}
We have that $\min(n_+(x),n_-(x))>0$ only if there exist integers $m$ and $m'$ with
$x\in I_{+}^m \cap I_{-}^{m'}$. By Corollary \ref{mSizeCor}, it must be the case that
$|m|,|m'| = O(|x|/s + 1).$ On the other hand, we have that $I_{+}^m$ is an interval
containing the point $ms$, and $I_{-}^{m'}$ is an interval containing the point $(m'+1/2)s$.
These points must differ by at least $s/2$, and therefore the sum of the lengths
of these intervals must be at least $s/2$. On the other hand, these intervals have length
$|m+1/2|\epsilon$ and $|m'+1/2|\epsilon$ respectively. Thus, $\min(n_+(x),n_-(x))>0$
can only occur if $s/2 = O(|x|\epsilon/s+\epsilon)$, which implies that
$x=\Omega(s^2/\epsilon)$, as desired.
\end{proof}

\begin{definition} \label{def:J}
We define $J$ to be $\mathbb{R} \backslash \bigcup_{m\in \mathbb{Z}} I^m_+$.
\end{definition}

We note that $J$ is a union of intervals.

\begin{lemma}
We have that $J$ is a union of $O(s/\epsilon)$ many intervals.
\end{lemma}
\begin{proof}
By Corollary \ref{JSupportCor}, $J$ is an interval $J_0 = [-O(s^2/\epsilon),O(s^2/\epsilon)]$ minus
all of the intervals $I^m_+$ that intersect $J_0$.
By Corollary \ref{mSizeCor}, $I_{+}^m$ intersects $J_0$ only when $|m| = O(s/\epsilon)$.
Thus, $J$ is an interval minus a union of $O(s/\epsilon)$ other intervals.
Thus, it is a union of $O(s/\epsilon)$ many intervals.
\end{proof}

We can now directly verify the properties of Proposition \ref{mainProp}.
\begin{itemize}
\item The definition of $J$ implies that $n_{+}(x)=0$ on $J$, which itself implies that $\mathcal{D}_{+}(x)=0$ for $x\in J$. The latter fact
combined with Corollary \ref{DRatioCor} imply Property~\ref{prop:1}.

\item Lemma \ref{supportIntersectLem} implies that the intersection of $J^c$ with the support of $\mathcal{D}_-$
consists only of points $x$ with $|x| = \Omega(s^2/\epsilon)$.
This fact and Corollary \ref{DBoundCor} imply Property~\ref{prop:2} \new{(by Gaussian concentration)}.

\item Property~\ref{prop:3} follows from Lemma \ref{DMomentsLem}.

\item Property~\ref{prop:4} follows from Corollary \ref{DBoundCor}.

\item Property~\ref{prop:5} follows from Lemma \ref{DL1Lem}.
\end{itemize}
This completes the proof of Proposition~\ref{mainProp}.
\end{proof}

\subsection{Putting Everything Together: Proof of Theorem~\ref{thm:main-formal}} \label{ssec:combine}
We now have the necessary ingredients to complete the proof of Theorem~\ref{thm:main-formal}.

\begin{proof}[Proof of Theorem~\ref{thm:main-formal}]
The proof leverages the SQ framework of Section~\ref{ssec:high-dim}
combined with the one-dimensional construction of Proposition \ref{mainProp}.

\paragraph{Parameter Setting}
Recall the parameters in the theorem statement.
We have that $\mathrm{OPT}>0$ and $M \in \mathbb{Z}_+$ are such that
$\log(M)/(\log\log(M))^3$ is at least a sufficiently large constant multiple of $\log(1/\mathrm{OPT})$.
Moreover, we define a parameter
$\tau$ which is set to $M^{-\new{\Theta}\left( \frac{\log(M)}{{\log\log(M)}^3}/\log(1/\mathrm{OPT}) \right)}$,
\new{where the implied constant in the exponent is sufficiently small}.

Let $C>0$ be a sufficiently large universal constant.
We define positive integers $m$ and $d$ as follows:
$m = {\lceil C\log(1/\tau) \rceil}$
and $d =  {\lceil  C\sqrt{\log(1/\mathrm{OPT})\log(1/\tau)\log\log(1/\tau)} \rceil}$.
Observe that
\begin{equation}\label{eqn:binom}
\binom{2d+m}{m} \leq m^{2d} =\exp(O(C\sqrt{\log(1/\mathrm{OPT})\log(1/\tau)(\log\log(1/\tau))^3})) \;.
\end{equation}
We note that if $\log(1/\tau)$ is a sufficiently small constant multiple of
$\frac{\log^2(M)}{(\log\log(M))^3 \log(1/\mathrm{OPT})}$,
then the RHS of~\eqref{eqn:binom} is less than $M$. Thus, by decreasing $M$ if necessary,
we can assume that $M=\binom{2d+m}{m}$.
Consider the Veronese mapping, denote by ${V}_{2d}:\mathbb{R}^m\rightarrow \mathbb{R}^M$,
such that the coordinate functions of ${V}_{2d}$ are exactly the monomials
in $m$ variables of degree at most $2d$.

\paragraph{Hard Distributions}
We can now formally construct the {family of high-dimensional distributions on labeled examples
that (1) corresponds to Massart halfspaces, and (2) is SQ-hard to learn}.
We define univariate measures $\mathcal{D}_{+}$ and $\mathcal{D}_{-}$ on $\mathbb{R}$,
as given by Proposition \ref{mainProp},
with $s$ and $\epsilon$ picked so that $s^2/\epsilon$ is a sufficiently large constant multiple
of $\sqrt{\log(1/\mathrm{OPT})}$ and $s/\epsilon$ a sufficiently small constant multiple of $d$
(for example, by taking $s=C^2 \sqrt{\log(1/\mathrm{OPT})}/d = \Theta(1/\sqrt{\log(1/\tau)\log\log(1/\tau)})$
and $\epsilon = C^3 \sqrt{\log(1/\mathrm{OPT})}/d^2$).

For a unit vector $v\in \mathbb{R}^m$, consider the distribution $\mathbf{P}_v^{\mathcal{D}_{+},\mathcal{D}_{-},p}$,
as in Proposition~\ref{prop:generic-sq}, with $p=\|\mathcal{D}_{+}\|_1/(\|\mathcal{D}_{+}\|_1 + \|\mathcal{D}_{-} \|_1)$.
\new{By property~\ref{prop:5} of Proposition~\ref{mainProp},
note that $\min (p, 1-p) = 1-p = \Theta(\eta)$.}

Our hard distribution is the distribution $(X',Y')$ on $\mathbb{R}^M \times \{\pm 1\}$ obtained
by drawing $(X,Y)$ from $\mathbf{P}_v^{\mathcal{D}_{+},\mathcal{D}_{-},p}$ and letting $X'={V}_{2d}(X)$ and $Y'=Y$.

We start by showing that this corresponds to a Massart halfspace.

\begin{claim}\label{clm:pv-Massart-LTF}
The distribution $(X',Y')$ on $\mathbb{R}^M \times \{\pm 1\}$  is a Massart LTF distribution
with optimal misclassification error $\mathrm{OPT}$ and Massart noise rate upper bound of $\eta$.
\end{claim}
\begin{proof}
{For a unit vector $v \in \mathbb{R}^m$,} let $g_{{v}}: \mathbb{R}^m \to \{\pm 1\}$ be defined as
$g_{{v}}(x)=-1$ if and only if $v \cdot x \in J$, {where $J$ is the union of intervals in the construction
of Proposition~\ref{mainProp}}. Note that $g_{{v}}$ is a degree-$2d$ PTF {on $\mathbb{R}^m$},
{since $g_v$ is a $(2d+1)$-piecewise constant function of $v \cdot x$}.
Therefore, there exists some LTF $L:\mathbb{R}^M \to \{\pm 1\}$ such that
$g_{{v}}(x)=L({V}_{2d}(x))$ for all $x \in \mathbb{R}^m$.

Note that our hard distribution returns $(X',Y')$ with $Y'=L(X')$,
unless it picked a sample corresponding to a sample of $\mathcal{D}_{-}$ coming from $J^c$,
which happens with probability at most $\zeta < \mathrm{OPT}$.
Additionally, suppose that our distribution returned a sample with $X'={V}_{2d}(X)$, for some $X\in \mathbb{R}^m$.
By construction, conditioned on this {event}, we have that $Y'=1$
with probability proportional to $\mathcal{D}_{+}(v\cdot X)$,
and $Y'=-1$ with probability proportional to $\mathcal{D}_{-}(v\cdot X)$.
We note that if $L({V}_{2d}(X))=1$, then $v\cdot X \not\in J$;
so, by Proposition~\ref{mainProp} property~\ref{prop:1}(b), this ratio is at least $1-\eta:\eta$.
On the other hand, if $L({V}_{2d}(X))=-1$, then $v\cdot X\in J$, so $\mathcal{D}_{+}(v\cdot X)=0$.
This implies that the pointwise probability of error $\eta(X')$ is at most \new{$\eta$},
completing the proof of the claim.
\end{proof}

We are now ready to complete the proof of our SQ lower bound.
It is easy to see that finding a hypothesis that predicts $Y'$ given $X'$
is equivalent to finding a hypothesis for $Y$ given $X$
(since $Y=Y'$ and there is a known 1-1 mapping between $X$ and $X'$).
The pointwise bounds on $\mathcal{D}_{+}$ and $\mathcal{D}_{-}$, {specifically properties~\ref{prop:4} and~\ref{prop:5}
in Proposition~\ref{mainProp},}
imply that
$$\chi^2(\mathcal{D}_{\pm}/\|\mathcal{D}_{\pm}\|_1 \, , \, G) \leq O(s/\epsilon)^2 = \mathrm{polylog}(M) \;.$$
The parameter $\nu$ in Proposition \ref{prop:generic-sq} is
$k!\exp(-\Omega(1/s^2)) = \exp(-\Omega(1/s^2))$ after
taking $k$ to be a sufficiently small constant multiple $\log(1/s)/s^2$.

Thus, by Proposition \ref{prop:generic-sq}, \new{in order to output a hypothesis with
error smaller than $\min(p, 1-p) = \Theta(\eta)$,}
any SQ algorithm either needs queries with accuracy better than
$$
\nu^2 + 2^{-k}(\chi^2(A,G)+\chi^2(B,G)) = \exp(-\Omega(\log(1/s)/s^2))\mathrm{polylog}(M) < \tau
$$
or a number of queries more than
$$
2^{\Omega(m)}\tau (\chi^2(A,G)+\chi^2(B,G)) > 1/\tau \;.
$$
Therefore, Proposition \ref{prop:generic-sq} implies that it is impossible for an SQ algorithm
to learn a hypothesis with error better than $\Theta(\eta)$
without either using queries of accuracy better than $\tau$
or making at least $1/\tau$ many queries.
This completes the proof of Theorem~\ref{thm:main-formal}.
\end{proof}

\subsection{Obtaining Optimal Error: The Case of Large $\eta$} \label{ssec:large-eta}

\new{
In this final subsection, we refine the construction of the previous subsections to obtain
a sharp lower bound of $\eta-o_{\eta}(1)$, when $\eta$ is close to $1/2$.
Here the term $o_{\eta}(1)$ goes to zero when $\eta$ approaches $1/2$. }
Specifically, we show:

\begin{theorem}[Sharp SQ Hardness of Massart Halfspaces for Large $\eta$] \label{thm:main-large-eta}
Let $\mathrm{OPT}>0$ and $M \in \mathbb{Z}_+$ be such that
$\log(M)/(\log\log(M))^3$ is at least a sufficiently large constant multiple of $\log(1/\mathrm{OPT})$.
\new{Let $c>0$ be any parameter such that $c \gg \sqrt{1/2-\eta}$.}
There exists a parameter $\tau \stackrel{{\mathrm {\footnotesize def}}}{=} M^{-\Omega_{\new{c}}\left( \frac{\log(M)}{{\log\log(M)}^3}/\log(1/\mathrm{OPT}) \right)}$
such that no SQ algorithm can learn the class of halfspaces on $\mathbb{R}^M$
in the presence of $\eta$-Massart noise, \new{where $\mathrm{OPT}< \eta \leq 1/2$,} within
error better than $1/2 - \new{c}$ using at most $1/\tau$ queries of tolerance $\tau$.
This holds even if the optimal classifier has misclassification error at most $\mathrm{OPT}$.
\end{theorem}

\new{Conceptually, Theorem~\ref{thm:main-large-eta} provides evidence that {\em even the constant factor}
(of $1$) in the error guarantee (of $\eta+\epsilon$) achieved by the Massart learner of~\cite{DGT19}
cannot be improved in general.}

The proof of Theorem~\ref{thm:main-large-eta} proceeds along the same lines
as the proof of Theorem~\ref{thm:main-formal}.
The main difference is in the choice of the one-dimensional moment-matching distributions.
For this, we use a construction that is qualitatively similar (though
somewhat more sophisticated)
to that used in the proof of Section~\ref{ssec:one-dim}.

Specifically, for some carefully chosen parameter $C>0$ (to be determined),
we define the positive measures:
$$
\mathcal{D}_+ := C \, (s/\epsilon) \,  \int_{0}^{\epsilon} \frac{G_{s+y, y/2}}{s+y} dy \;,
$$
and
$$
\mathcal{D}_- := (s/\epsilon) \, \int_{0}^{\epsilon} \frac{G_{s+y,(y+s)/2}}{s+y} dy \;.
$$
As a refinement of Corollary \ref{DSizeCor}, we obtain the following.
\begin{corollary} For all $x \in \mathbb{R}$, we have that
$$
\mathcal{D}_+(x) = C g(x) (s^2/\epsilon) n_+(x)/(|x|+1)(1+O(\epsilon/(|x|+1)))
$$
and
$$
\mathcal{D}_-(x) = g(x) (s^2/\epsilon) n_-(x)/(|x|+1)(1+O(\epsilon/(|x|+1))) \;.
$$
\end{corollary}
\begin{proof}
This follows from the explicit formulas for $\mathcal{D}_+$ and $\mathcal{D}_-$ (Lemma~\ref{lem:formulas-d})
along with the fact that for
$x\in I_m^{\pm}$, $1/|m|$ and $1/|m+1/2|$ are $s/(|x|+1)(1+O(\epsilon/(|x|+1)))$.
\end{proof}

Using the above corollary, we obtain the following.

\begin{corollary}
For all $x \in \mathbb{R}$, we have that
$\mathcal{D}_+(x)/\mathcal{D}_-(x) = C \, q(x)(1+O(\epsilon/(|x|+1)))$, where
$q(x) = n_{+}(x)/n_{-}(x)$ is a rational number
with numerator and denominator at most $O(|x|/s+1)$.
\end{corollary}

We want to guarantee that for all $x\in \mathbb{R}$ it holds that
$\mathcal{D}_+(x)/\mathcal{D}_-(x) \not \in [\eta/(1-\eta),(1-\eta)/\eta]$.
We note that this condition automatically holds for $|x|$ less than a sufficiently
small constant multiple of $s^2/\epsilon$,
as in this range we have that $\min(n_+(x),n_-(x))=0$.
For points $x$ outside this range, we have that
$\mathcal{D}_{+}(x)/\mathcal{D}_{-}(x) = C \, q(x) (1+O(\epsilon/s)^2)$.
Furthermore, since $|n_+(x)-n_-(x)|\leq 1$, the latter
implies that in this range $\mathcal{D}_+(x)/\mathcal{D}_{-}(x)$ is always one of:
\begin{itemize}
\item $C(1+O(\epsilon/s)^2)$ \;,
\item $C(1+1/m)(1+O(\epsilon/s)^2)$, for some integer $m$,
\item $C(1-1/m)(1+O(\epsilon/s)^2)$, for some integer $m$.
\end{itemize}
We will arrange that this quantity is always in the appropriate range
by picking the parameter $C$,
so that for some well chosen $m_0$
we have that
$$
C(1-1/m_0)(1+O(\epsilon/s)^2) \leq \eta/(1-\eta) \textrm{, and   } C(1-1/(m_0+1))(1-O(\epsilon/s)^2) \geq (1-\eta)/\eta \;.
$$
If the above holds, it is easy to see that $\mathcal{D}_+(x)/\mathcal{D}_{-}(x)$ will never be in the range
$[\eta/(1-\eta),(1-\eta)/\eta]$ for any value of $x$. In order to arrange this, we set $C$ to satisfy
$$
C(1-1/m_0)(1+O(\epsilon/s)^2) = \eta/(1-\eta) \;.
$$
In order for the second condition to hold, it must be the case that
$$
\left(\frac{1-1/(m_0+1)}{1-1/m_0} \right)(1-O(\epsilon/s)^2) > ((1-\eta)/\eta)^2 = 1+O(1/2-\eta) \;.
$$
For the latter to be true, it must hold that $1/m_0^2 $ is at least
a sufficiently large constant multiple of $(1/2-\eta)+(\epsilon/s)^2$,
or that $m_0$ is at most a sufficiently small constant
multiple of $\min(s/\epsilon, \sqrt{1/2-\eta})$.

In particular, if we take $m_0$ to be \new{at most} a sufficiently small constant
multiple of $1/\sqrt{1/2-\eta}$ and ensure that $\epsilon/s$ is sufficiently small,
this construction can be made to work with $C= 1+ \new{1/m_0}$.

We then let $J$ be the set of points $x \in \mathbb{R}$ for which $\mathcal{D}_{-}(x) > \mathcal{D}_{+}(x)$.
It is easy to see that $J =\{x: m_0 \geq n_-(x) > n_+(x)\}$,
and from this it can be seen that $J$ is a union of $O(m_0 s/\epsilon)$ intervals.
As before, $\mathcal{D}_{+}$ and $\mathcal{D}_{-}$ approximately match many moments
with a Gaussian and the mass of $\mathcal{D}_{+}$ on $J$ and $\mathcal{D}_{-}$ on $J^c$
are both supported on points $x$ such that
$|x| \geq \Omega(s^2/\epsilon)$, and thus have mass $\exp(-\Omega(s^4/\epsilon^2))$.

Furthermore, we have that $\mathcal{D}_{-}(x)/\mathcal{D}_{+}(x) > (1-\eta)/\eta$ for $x \in J$ and
$\mathcal{D}_{+}(x)/\mathcal{D}_{-}(x) > (1-\eta)/\eta$ for $x \in J^c$. Therefore, the appropriate hidden-direction
distribution is a degree-$O(m_0 s/\epsilon)$ PTF with at most $\eta$ Massart noise.

Finally, it is not hard to see that $\|\mathcal{D}_+\|_1/\|\mathcal{D}_-\|_1 = 1+\new{1/m_0}$.
Therefore, \new{by following the arguments of Section~\ref{ssec:combine} mutatis-mutandis},
it follows that for any constant $\eta<1/2$ it is SQ-hard to learn an LTF with $\eta$-Massart noise
to error better than \new{$1/2-c$ for any $c \gg \sqrt{1/2-\eta}$},
even when $\mathrm{OPT}$ is almost polynomially small in the dimension.
This completes the proof of Theorem~\ref{thm:main-large-eta}. \qed

\section{Conclusions and Future Work} \label{sec:conc}

In this paper, we gave a super-polynomial Statistical Query (SQ) lower bound
with near-optimal inapproximability gap for the fundamental problem of
(distribution-free) PAC learning Massart halfspaces.
Our lower bound provides strong evidence that known algorithms
for this problem are essentially best possible.
An obvious technical open question is whether the hidden constant factor
in the $\Omega(\eta)$-term of our lower bound
can be improved to the value $C=1$ for all $\eta>0$.
(Recall that we have shown such a bound for $\eta$ close to $1/2$.)
This would match known algorithms {\em exactly}, specifically showing that the error of $\eta+\epsilon$
cannot be improved even for small values of $\eta>0$.

Interestingly, SQ lower bounds are the {\em only known} evidence of hardness
for our Massart halfspace learning problem. Via a recent reduction~\cite{BBHLS20}, our SQ
lower bound implies a similar low-degree polynomial testing lower bound for the problem.
An interesting open question is to prove similar hardness results against
families of convex programming relaxations (obtained, e.g., via the Sum-of-Squares framework).
Such lower bounds would likely depend on the underlying optimization formulation of the learning problem.

A related question is whether one can establish reduction-based computational hardness for learning
halfspaces in the presence of Massart noise. Daniely~\cite{Daniely16} gave such a reduction for the (much more challenging) problem of agnostically learning halfspaces,
starting from the problem of strongly refuting random XOR formulas.
It currently remains unclear whether the latter problem is an appropriate starting point
for proving hardness in the Massart model. That said, obtaining reduction-based hardness
for learning Massart halfspaces is left as an interesting open problem.

\clearpage

\bibliographystyle{alpha}