# Two-stage Human Activity Recognition on Microcontrollers with Decision Trees
and CNNs

Francesco Daghero  DAUIN, Politecnico di Torino
Turin, Italy
<EMAIL_ADDRESS>Daniele Jahier Pagliari  DAUIN, Politecnico di
Torino
Turin, Italy
<EMAIL_ADDRESS>Massimo Poncino  DAUIN, Politecnico di Torino
Turin, Italy
<EMAIL_ADDRESS>
###### Abstract

Human Activity Recognition (HAR) has become an increasingly popular task for
embedded devices such as smartwatches. Most HAR systems for ultra-low power
devices are based on classic Machine Learning (ML) models, whereas Deep
Learning (DL), although reaching state-of-the-art accuracy, is less popular
due to its high energy consumption, which poses a significant challenge for
battery-operated and resource-constrained devices. In this work, we bridge the
gap between on-device HAR and DL thanks to a hierarchical architecture
composed of a decision tree (DT) and a one dimensional Convolutional Neural
Network (1D CNN). The two classifiers operate in a cascaded fashion on two
different sub-tasks: the DT classifies only the easiest activities, while the
CNN deals with more complex ones. With experiments on a state-of-the-art
dataset and targeting a single-core RISC-V MCU, we show that this approach
allows to save up to 67.7% energy w.r.t. a ”stand-alone” DL architecture at
iso-accuracy. Additionally, the two-stage system either introduces a
negligible memory overhead (up to 200 B) or on the contrary, reduces the total
memory occupation.

###### Index Terms:

Machine Learning, Adaptive Inference, Microcontrollers, Energy Efficiency

©2022 IEEE. Personal use of this material is permitted. Permission from IEEE
must be obtained for all other uses, in any current or future media, including
reprinting/republishing this material for advertising or promotional purposes,
creating new collective works, for resale or redistribution to servers or
lists, or reuse of any copyrighted component of this work in other works.
Accepted as a conference paper at the IEEE 2022 PRIME Conference.

##  I Introduction and Related Works

Human Activity Recognition (HAR) based on Inertial Measurements Units (IMUs)
has become an increasingly popular feature for smart devices such as fitness
trackers and smartwatches. A HAR task consists of determining the activity
performed by an user in a specific time-window of the input signal. This is
generally performed through Machine Learning (ML) [1, 2] and more recently
Deep Learning (DL) [1, 3], with the latter generally achieving state-of-the-
art accuracy.

As for many other tasks in the Internet of Things (IoT) world, HAR benefits
from an edge-centric approach, that is, from performing the full ML inference
on the same device collecting the sensors readings. In this way, there is no
need to transmit the data over possibly unstable or unreachable networks, thus
making the inference latency more predictable. Additionally, possibly
sensitive information don’t have to be transmitted, increasing the application
security. Finally, avoiding the data transmission brings an additional
advantage in terms of energy efficiency: wireless connectivity is in fact
power-hungry, generally consuming much more than performing the computations
locally. This is particularly beneficial since edge devices are often battery-
powered.

However, directly deploying a HAR ML model tailored for the cloud on an
embedded device is often difficult. Those devices are in fact typically based
on ultra-low-power Microcontrollers (MCUs) with tight memory constraints and
relatively low clock frequencies. For this reason, most HAR implementations on
embedded devices are based on simple classifiers such as Decision Trees (DTs).
These shallow ML models require only a few compare-and-branch operations for
inference, and resulting in low latency and energy consumption. Additionally,
their memory requirements are also orders of magnitude less than other types
of classifiers. However, they rarely reach very high accuracies on complex
tasks.

On the other hand, DL approaches have shown promising results for HAR [1, 3,
2], achieving state-of-the-art accuracies (significantly higher than tree-
based models) on several datasets. However, most DL models proposed in other
works are impossible to deploy on MCUs, requiring $>1$ million parameters and
floating point operations for inference [3]. This, in turn, translates into
unacceptable latency and energy consumption for IoT devices.

To bridge this gap, several works have introduced optimizations aimed at
reducing the complexity of DL models and making them compatible with edge
devices. Among the most popular there are quantization and pruning [4, 5],
which modify the models statically before deployment, either at training time
or post-training, respectively reducing the complexity of the network through
the use of low-precision arithmetic or removing redundant parameters.

Orthogonal to such approaches, dynamic (or adaptive) optimization techniques
leverage the varying complexity of inputs in order to save energy at runtime.
The key intuition is that performing an inference with an accurate yet energy
demanding model is wasteful for easy inputs, while naively shrinking the
classifier may lead to a deterioration in predictions’ quality for hard
inputs. Additionally, easy inputs are often far more common than hard ones in
real-word situations (e.g. for HAR the activity ”laying” is far more frequent
than ”walking upstairs”), thus making adaptive approaches even more effective
in terms of energy efficiency.

Most existing dynamic inference systems are based on sequentially executing
multiple models of increasing complexity on each input, all performing the
same task, and stopping the process as soon as a sufficient output confidence
is reached. The multiple models can be separate [6] or share weights, using
variable-width [7], variable-precision [8], or early-exit [9, 10] mechanisms.
Alternatively, so-called “hierarchical classifiers” split an inference task
into different sub-tasks based on the input. An example of this approach is
[11], which introduces a framework based on several cascaded classifiers of
increasing complexity, each working on an increasingly more difficult sub-
task, constructed so that easier and more common inputs stop earlier in the
cascade, reducing the average energy consumption.

In this paper, we follow the latter approach, proposing a novel type of
adaptive architecture tailored for HAR tasks. Specifically, we combine a DT
and a 1-dimensional (1D) Convolutional Neural Network (CNN). The first is
trained to select only among the easiest activities, and output a generic
fallback class for all other inputs. Only when the fallback class is predicted
by the DT, the CNN is activated, performing an inference pass on the same
input. We test our approach on a single-core RISC-V MCU and on a state-of-the-
art HAR dataset [12], showing that we are able to save up to 67.7% energy at
iso-accuracy, and with a negligible memory overhead, with respect to a static
DL approach. More generally, our adaptive system is Pareto optimal when
compared to multiple static CNN architectures, both in the energy versus
accuracy and memory versus accuracy planes.

##  II Proposed Method

Figure 1: High-level overview of the two-stage hierarchical inference
architecture. Easy classes are classified by the DT (left), while complex ones
are left to the CNN (right). Figure 2: Schematic view of the proposed training
and deployment flow.

This work proposes the first two-stage hierarchical, hybrid ML/DL system for
HAR, to our knowledge.

Fig. 1 shows an high-level scheme of the solution, which mixes a DT with a
1D-CNN, each working on a different sub-task, rather than on the whole set of
activities. Specifically, the DT always performs the first inference on each
new input datum, looking for easy activity classes. For example, inputs
corresponding to the “laying” activity can be intuitively recognized looking
just at the orientation and amount of movement detected by the accelerometer.
To cover more complex activities, the DT is trained to output a generic
“fallback” class, which can be interpreted as: “the input does not belong to
any of the easy classes”. When the DT output is different from “fallback”, the
inference terminates immediately, using the predicted class as final result.
On the contrary, when the fallback class is predicted, the 1D CNN is activated
and applied to the same input, in order to distinguish among more complex
activities (e.g., stairs climbing, running, cycling, etc).

The average energy consumption of this hierarchical model can be computed with
the following equation:

$E=E_{DT}+P_{fallback}*E_{CNN}$ (1)

where $E_{x}$ denotes the inference energy of $x$, and $P_{fallback}$ denotes
the probability of an input being classified as ”fallback” by the DT, thus
enabling the CNN. Since the DT is significantly less computationally expensive
than the CNN ($E_{DT}<<E_{CNN}$), large energy savings are obtained for easy
inputs, which only require the execution of the first “stage”. Moreover, the
latter are often the majority in real-life scenarios (we sleep for more hours
than we jump or climb stairs), meaning that the total savings will also be
considerable.

Additionally, with respect to a standard, single-stage classifier, our second-
stage CNN operates on a reduced set of classes (only the complex ones), which
reduces both the number of inference operations and the number of parameters
of last fully-connected layer. The former further cuts the energy cost of the
system, while the latter helps compensating the memory overhead introduced by
the presence of the DT.

###  II-A Training and Deployment Flow

Fig. 2 shows the training and deployment flow that we propose for the two-
stage adaptive system just described, which is composed of five main steps.

#### 1\. DT-based Task Decomposition

In the first phase, we identify the easy and hard classes that will be later
assigned to the DT and CNN respectively. To this end, we train and optimize
the hyper-parameters of a DT on the full task (i.e., on all $M$ activity
classes). Namely, we select the tree depth that yields the best classification
results on the full training set, by means of an exhaustive grid search, made
possible by the limited size of HAR datasets. In our experiments, we explore
depth values in [2,10]. Then, we select as easy classes the $M_{easy}<M$
static activities for which the complete DT achieves the largest F1 score. In
general, the number of easy classes is a design parameter that should be
explored, but in this preliminary work, we fix it to $M_{easy}=2$. All other
classes are considered hard.

#### 2\. Sub-tasks Training Sets Generation

Next, we generate the training sets for the DT and CNN. The former is obtained
keeping samples relative to all easy classes unchanged, and modifying hard
samples so that they all have the same label, corresponding to the fallback
class. The CNN training set, instead, is simply obtained removing all easy
classes samples, since those are not considered in the second inference stage.

#### 3\. Final DT Selection and Training

We then perform a second set of trainings and depth optimizations on the DT,
this time on the modified training set containing only easy-classes and
fallback examples. We look once again for the model that maximizes the
classification score, using grid search.

#### 4\. CNN Pareto Exploration

For what concerns the CNN, we perform a similar search, but in this case
rather than only selecting the most accurate model, we extract the entire
Pareto frontier in the energy versus classification score space. This
difference comes from the fact that the second stage of the hierarchical model
is by far the most computationally expensive. Therefore, building the
hierarchical system starting from different Pareto-optimal CNNs is the easiest
way to obtain different accuracy versus energy consumption trade-offs, as
shown in Sec. III. The CNN architecture exploration is performed starting from
a common template, based on a classic network structure [13], composed of
three convolutional blocks (each including a convolution, batch normalization
and max-pooling) and a final fully-connected layer. We explore variants of
this template obtained changing the number of channels and the kernel size in
each convolutional layer. Specifically, we consider all possible combinations
of power-of-2 channels in $[2,...,128]$ and kernel sizes 7 or 15. The max-
pooling stride and width are left fixed at 2.

#### 5\. MCU Deployment

Lastly, we deploy the selected DT and one of the Pareto-optimal CNNs onto the
target MCU, combining them with the scheme of Fig 1, using optimized libraries
(described below) to implement both classifiers.

##  III Experimental Results

We target a popular public HAR dataset named UCI HAPT [12], featuring 958500
samples collected from the accelerometer and gyroscope of an Android phone.
The data has been collected with a sampling frequency of 50 Hz from 30 subject
performing 12 different activities. We keep the same train/test split proposed
by the authors and split the data in non overlapping windows of 5 s, obtaining
inputs of size 250x6. For this dataset, the 2 classes identified as easy by
our procedure, hence those classified by the DT, are sitting and laying, which
result in the highest F1-score (above 85%) on the training set. Together,
these two activities account for $\approx$ 30% of both training and testing
samples.

As deployment target, we select the single-core, ultra-low-power, RISC-V MCU
Quentin [14], with characteristics close to those of common embedded HAR
devices. The MCU has 520 kB of memory, and our results are obtained with the
core running at 205.1 MHz, with a supply voltage of 0.54 V. In these
conditions, the system consumes 3.8 mW of active power.

We train our DTs and CNNs in Python, before converting the trained models to
optimized C code for the target MCU. For this conversion, we use the library
described in [15] for the 1D CNN, while the DT and RF implementations are
described in [1]. Both libraries are specifically tailored for the target
hardware, leveraging the available SIMD and DSP-oriented instruction set
extensions.

###  III-A Energy and memory comparison

Figure 3:  Accuracy versus average energy consumption and total memory
occupation results, for the proposed two-stage method and for a static CNN-
based approach.

Fig. 3 shows the results obtained by our two-stage architecture in terms of
classification accuracy versus inference energy consumption and memory
occupation on the target MCU. Specifically, each blue triangle represents a
hierarchical system built combining the DT determined in Step 3 of Fig. 2
(always the same) and one of the different Pareto-optimal CNN architectures
found in Step 4 of Sec. II-A. For comparison, the two graphs also report the
results obtained with different static CNNs derived from the same search
space, and trained directly on all activity classes (red crosses). The dashed
black line identifies the global Pareto front. Energy results refer to the
average consumption for a single inference, over the entire test set.

On the energy side, Fig. 3 shows that our approach occupies most of the Pareto
frontier, with the exception of a single architecture around 85% accuracy.
Namely, we are able to reduce the average energy per inference by up to 67.7%
at iso-accuracy, or to improve the accuracy by up to 12.34% for the same
average energy. Further, our most accurate adaptive system outperforms the
best static CNN (+3% accuracy) with lower energy consumption. This result is
obtained thanks to the fact that the DT achieves a classification accuracy of
92% on the “easy activities” sub-task, while having negligible inference
energy costs (341x less than the smallest CNN).

Memory results are similar, showing that the presence of an additional DT in
our two-stage system yields negligible overheads. Specifically, the DT
requires a total of 0.2kB of memory, yielding a maximum overhead of around 9%
w.r.t to the smallest static CNN ($\leq 3$ kB). At the opposite side of the
Pareto front, thanks to the reduced dimension of the last CNN fully-connected
layer (given by the reduced number of activities classified), the total memory
of the system is instead reduced by up to 64% for the same accuracy.

Figure 4:  Accuracy versus average energy consumption and total memory
occupation results for the proposed two-stage method and for a Random Forest
classifier.

Figure 4 compares our method with a fully tree-based solution, consisting
either of a single DT or of a Random Forest (RF) ensemble [1]. Precisely, the
green curve shows the Pareto front obtained training all RFs with a number of
trees from 1 (single DT) to 15, and depths in the $[2,20]$ interval. The blue
curve is the Pareto front of our adaptive method. As explained in Sec. I,
tree-based models are expected to have lower energy consumption than DL ones,
due to their lightweight computations, as confirmed by the graphs. However,
also as expected, these models are unable to achieve comparable accuracy to a
DL-based method within the memory constraints of a typical MCU. Indeed, even
the largest RFs, which occupy more memory than our adaptive system, cannot
achieve more than 71% accuracy.

###  III-B Detailed Deployment Results

Table I reports the detailed deployment results, in terms of memory
occupation, energy consumption, and inference latency, of the most accurate
version of our adaptive system, and of the most accurate static CNN (Base
rows). The results show that, while obtaining a +3% accuracy increase, the
adaptive system can reduce the average energy and latency per inference by
31.6% even at maximum accuracy. Additionally, in order to show the potential
advantages of such a system in a real-world scenario, we repeat the experiment
after synthetically over-sampling laying and sitting inputs (i.e., the easy
classes) in the test set by 10x and 20x. In those settings, the accuracy
improvement reaches +4%, and the energy/latency reductions increase to 76% and
83% respectively.

| Mode | Acc. | Memory[kB] | Energy[$\mu$j] | Latency[ms]
---|---|---|---|---|---
Base | Ours | 0.87 | 37.2 | 17.9 | 4.7
Static | 0.84 | 37.8 | 26.2 | 6.9
10x | Ours | 0.89 | 37.2 | 6.2 | 1.6
Static | 0.85 | 37.8 | 26.2 | 6.9
20x | Ours | 0.90 | 37.2 | 4.4 | 1.2
Static | 0.86 | 37.8 | 26.2 | 6.9
TABLE I: Detailed deployment results on the original and synthetically
augmented test data.

##  IV Conclusions

We have presented a novel, two-stage HAR system for MCUs, featuring a small DT
tree cascaded with a 1-dimensional CNN. Our approach leverages the different
input complexity to save energy at inference time, switching on the CNN only
when needed. Compared to a static CNN, we reduce the average energy per
inference by up to 67.7% at iso-accuracy on a state-of-the-art HAR dataset.
With respect to a pure tree-based model, our approach occupies a different
portion of the design space, yielding much higher accuracy for the same memory
occupation.

## References

  * [1] F. Daghero _et al._ , “Ultra-compact binary neural networks for human activity recognition on risc-v processors,” in _18th ACM CF_ , 2021, p. 3–11.
  * [2] W. Sousa _et al._ , “A comparative analysis of the impact of features on human activity recognition with smartphone sensors,” in _WebMedia_ , 2017, pp. 397–404.
  * [3] H. Thu _et al._ , “Hihar: A hierarchical hybrid deep learning architecture for wearable sensor-based human activity recognition,” _IEEE Access_ , vol. 9, pp. 145 271–145 281, 2021.
  * [4] B. Jacob _et al._ , “Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference,” in _IEEE CVPR_ , 2018.
  * [5] P. Molchanov _et al._ , “Pruning convolutional neural networks for resource efficient inference,” _arXiv preprint arXiv:1611.06440_ , 2016.
  * [6] E. Park _et al._ , “Big/little deep neural network for ultra low power inference,” in _IEEE CODES+ ISSS_ , 2015, pp. 124–132.
  * [7] H. Tann _et al._ , “Runtime configurable deep neural networks for energy-accuracy trade-off,” in _IEEE CODES+ ISSS_ , 2016, pp. 1–10.
  * [8] D. Jahier Pagliari _et al._ , “Dynamic Bit-width Reconfiguration for Energy-Efficient Deep Learning Hardware,” in _ACM ISLPED_ , 2018, pp. 47:1—-47:6.
  * [9] S. Teerapittayanon _et al._ , “Branchynet: Fast inference via early exiting from deep neural networks,” in _23rd IEEE ICPR_ , 2016, pp. 2464–2469.
  * [10] F. Daghero _et al._ , “Adaptive Random Forests for Energy-Efficient Inference on Microcontrollers,” in _29th VLSI-SoC_ , 2021, pp. 1–6.
  * [11] K. Goetschalckx _et al._ , “Optimized hierarchical cascaded processing,” _IEEE JETCAS_ , vol. 8, no. 4, pp. 884–894, 2018.
  * [12] J.-L. Reyes-Ortiz _et al._ , “Transition-aware human activity recognition using smartphones,” _Neurocomputing_ , vol. 171, pp. 754–767, 2016.
  * [13] Y. LeCun _et al._ , “Gradient-based learning applied to document recognition,” _Proc. of the IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998\.
  * [14] A. Di Mauro _et al._ , “Always-on 674$\mu$ w@ 4gop/s error resilient binary neural networks with aggressive sram voltage scaling on a 22-nm iot end-node,” _IEEE TCAS-I_ , vol. 67, no. 11, pp. 3905–3918, 2020.
  * [15] A. Burrello _et al._ , “TCN Mapping Optimization for Ultra-Low Power Time-Series Edge Inference,” in _IEEE/ACM ISLPED_ , 2021, pp. 1–6.


# No Wrong Turns: The Simple Geometry Of Neural Networks Optimization Paths

Charles Guille-Escuret
Mila, Université de Montreal
&Hiroki Naganuma∗
Mila, Université de Montreal
&Kilian Fatras
Mila, McGill University
&Ioannis Mitliagkas
Mila, Université de Montreal, CIFAR AI Chair
equal contributions

###### Abstract

Understanding the optimization dynamics of neural networks is necessary for
closing the gap between theory and practice. Stochastic first-order
optimization algorithms are known to efficiently locate favorable minima in
deep neural networks. This efficiency, however, contrasts with the non-convex
and seemingly complex structure of neural loss landscapes. In this study, we
delve into the fundamental geometric properties of sampled gradients along
optimization paths. We focus on two key quantities, which appear in the
restricted secant inequality and error bound. Both hold high significance for
first-order optimization. Our analysis reveals that these quantities exhibit
predictable, consistent behavior throughout training, despite the
stochasticity induced by sampling minibatches. Our findings suggest that not
only do optimization trajectories never encounter significant obstacles, but
they also maintain stable dynamics during the majority of training. These
observed properties are sufficiently expressive to theoretically guarantee
linear convergence and prescribe learning rate schedules mirroring empirical
practices. We conduct our experiments on image classification, semantic
segmentation and language modeling across different batch sizes, network
architectures, datasets, optimizers, and initialization seeds. We discuss the
impact of each factor. Our work provides novel insights into the properties of
neural network loss functions, and opens the door to theoretical frameworks
more relevant to prevalent practice.

##  1 Introduction

Figure 1: Cosine similarities between the gradients $G_{t}$ sampled at step
$t$ and the difference $(w_{t}-w_{T})$ between current weights and final
weights, averaged over each epoch. The shaded regions denote the range from
minimum to maximum values observed at each epoch. The results are presented
for a selection of scenarios: (top left) varying depths and widths of ResNet
on ImageNet, (top right) different batch sizes on WikiText-2 using a
Transformer, (bottom left) a range of optimizers on CIFAR-10 using ResNet-18,
and (bottom right) distinct architectures on Vaihingen semantic segmentation.
This figure highlights the stability of the cosine similarity throughout most
of training, suggesting it as a fundamental characteristic of neural loss
landscapes.

Despite the theoretical complexity of their loss landscapes, deep neural
networks have demonstrated remarkable empirical reliability across a broad
range of applications. Blum and Rivest [3] proved decades ago that neural
network training is NP-hard. The intricacy of their loss functions, especially
the non-convexity implying potential bad local minima and saddle points, has
led to an enduring conundrum concerning the empirical efficiency of stochastic
first-order optimization methods for training neural networks.

Numerous studies have strived to reconcile this apparent contradiction,
focusing on the behaviors of stochastic gradient descent (SGD) and its
variants at local minima and saddle points [35, 21]. The central hypothesis in
these works posits that the efficiency of training arises from the ability of
these algorithms to navigate complex loss landscapes adeptly and manage non-
convexity.

Conversely, other investigations have empirically found loss landscapes to be
simpler than their theoretical complexity might suggest [31]. Notably,
Goodfellow et al. [14] observed that “in fact, on a straight path from
initialization to solution, a variety of state of the art neural networks
never encounter any significant obstacles.“

Notwithstanding, our current understanding of how neural loss landscapes are
empirically simpler than expected remains quite limited. There is yet to
emerge a robust mathematical characterization of this empirical simplicity.
Consequently, we contend that the theoretical assumptions currently in use
fail to accurately capture the objective functions typical in deep learning.
This discrepancy is a significant barrier to applying theoretical insights
effectively in the optimization of neural networks.

One such common assumption, smoothness, is illustrative of this gap. Despite
its popularity, smoothness is encumbered by several limitations: it is
computationally intensive to approximate for large neural networks, and
necessitates additional assumptions such as bounded gradients for theoretical
guarantees in stochastic settings [37, 44] although recent works have tried to
discard them [34, 30]. Finally, recent findings suggesting certain directional
sharpness in neural networks [8] call into question the suitability of
smoothness as a measure of their simplicity.

To address these issues, our study undertakes an empirical analysis of the
geometric properties of the loss function in regions traversed by first-order
optimization algorithms. Our focus is on a variant of the quantities involved
in the Restricted Secant Inequality (RSI) [48] and Error Bound (EB) [32],
which pertain to the relationship between sampled gradients, current iterate,
and final iterate of the optimization sequence. Our findings indicate that
these quantities and their ratio exhibit stable, predictable patterns
throughout training across diverse settings, thereby quantitatively
characterizing the simplicity of neural loss landscape geometry. Furthermore,
these quantities offer several advantages over smoothness, including efficient
estimations post-training, inherent compatibility with stochasticity due to
direct measurement on sampled gradients, and a well-behaved empirical nature
that still allows the derivation of theoretical results such as linear
convergence or the prescription of learning rate schedules.

Our key contributions are as follows:

  * •

We devise an experimental procedure for examining the geometry of optimization
paths on common architectures. We assume almost-everywhere differentiability,
but not smoothness.

  * •

We execute experiments across a range of realistic deep learning settings,
identifying consistently verified properties. For instance, the cosine
similarity between the negative stochastic gradient and the direction to the
final iterate is almost always positive and exhibits remarkable stability
across iterations and epochs.

  * •

We demonstrate how our empirical investigations can inform the prescription of
learning rate schedules, aligning with established empirical knowledge.

  * •

We provide an extensive discussion on the implications and limitations of our
findings.

Collectively, our work quantifies crucial geometric properties of stochastic
gradients along deep learning optimization paths, underlining their importance
in understanding neural network optimization and enhancing current
methodologies.

##  2 Related Work

Our investigation centers on the application of $\operatorname{RSI}$ and
$\operatorname{EB}$ to enhance our comprehension of the geometric principles
governing neural network optimization. Consequently, our work intersects with
previous research on neural loss landscapes and the utilization of
$\operatorname{RSI}$ and $\operatorname{EB}$ in optimization.

RSI and EB: The study of $\operatorname{RSI}$ and $\operatorname{EB}$ for
first-order optimization is not new. $\operatorname{RSI}$ [48] has been
applied in numerous theoretical works [46, 43, 47, 22]. $\operatorname{EB}$
[32] has seen less extensive study [9], possibly due to the dominance of
smoothness —a condition stronger than $\operatorname{EB}$— in the field. It
should not be confused with error bounds on the distance to a set, a term also
prevalent in optimization literature [38, 49]. Both $\operatorname{RSI}$ and
$\operatorname{EB}$, along with other conditions, were analyzed in Guille-
Escuret et al. [15]. Furthermore, it was demonstrated in Guille-Escuret et al.
[16] that gradient descent is optimal for the class of functions defined by
this pair of conditions.

Neural Loss Landscape Geometry: The intricacies of neural loss landscapes have
been a focal point of research since the emergence of deep learning. Efforts
have ranged from loss landscape visualizations [27] to investigations of low
loss basin connectivity [13] and linear mode connectivity [12]. While prior
research has noted the seeming simplicity of loss landscape geometry along
optimization paths [31, 14], these observations often involve straightforward
phenomena such as monotonic decrease along linear interpolations. Our work
takes this approach a step further by studying quantifiable properties with
theoretical implications. Additionally, others have examined the geometric
properties of neural loss landscapes in the near-infinite width, or Neural
Tangent Kernel (NTK), regime [20, 26]. These studies suggest that neural
network training can be approximated by linear dynamics or that the loss
surface adheres to the Polyak-Łojasiewicz condition [28]. Unfortunately, this
scenario was found to be distinct from empirical settings [4], although recent
studies have delved into the evolution of the NTK under more realistic
conditions [11]. We also note the active research direction regarding the
influence of BatchNorm on the optimization trajectory [42, 18].

##  3 Background

The training of a neural network on a dataset comprised of $n$ examples can
typically be formulated as the finite-sum optimization problem

$\min_{w\in\mathbb{R}^{d}}\mathcal{L}(w):=\frac{1}{n}\sum_{i=1}^{n}l_{i}(w),$
(1)

where $w$ are the parameters of the neural network, $\mathcal{L}$ is the
empirical risk, and $l_{i}$ corresponds to the loss function for the $i$-th
data sample, for $i=1,\dots,n$. We denote the empirical risk with respect to
any minibatch $\mathcal{B}\subseteq[n]$ of size $m$ as
$\mathcal{L}_{\mathcal{B}}:=\frac{1}{m}\sum_{i\in\mathcal{B}}l_{i}$.
Throughout this work, we assume the loss to be differentiable, but we do not
require it to be smooth.

We now recall the definitions of $\operatorname{RSI}^{-}$ and
$\operatorname{EB}^{+}$ as provided by Guille-Escuret et al. [15]. Given an
objective function $\mathcal{L}$ with a convex set of global minima
$\mathcal{X}^{\star}$, and letting $w_{p}^{\star}$ be the orthogonal
projection of $w$ into $\mathcal{X}^{\star}$,

######  Definition 3.1 (Lower Restricted Secant Inequality).

Let $\mu>0$. $\mathcal{L}\in\operatorname{RSI}^{-}(\mu)$ iff:

$\textstyle\forall
w\in\mathbb{R}^{d},\nabla\mathcal{L}(w)^{T}(w-w_{p}^{\star})\geq\mu\left\|w-w_{p}^{\star}\right\|_{2}^{2}.$
(2)

######  Definition 3.2 (Upper Error Bounds).

Let $L>0$. $\mathcal{L}\in\operatorname{EB}^{+}(L)$ iff:

$\textstyle\forall
w\in\mathbb{R}^{d},\left\|\nabla\mathcal{L}(w)\right\|_{2}\leq
L\left\|w-w_{p}^{\star}\right\|_{2}.$ (3)

The classes of functions $\operatorname{RSI}^{-}$ and $\operatorname{EB}^{+}$
are thus defined in the literature as those respecting the above bounds over
the entire parameter space. However, in this work, our focus lies not merely
on their extremal values but on the local quantities bounded by
$\operatorname{RSI}^{-}$ and $\operatorname{EB}^{+}$.

For simplicity, we refrain from introducing new terminology, and henceforth
denote these quantities as $\operatorname{RSI}(G,w,w^{\star})$ and
$\operatorname{EB}(G,w,w^{\star})$, where $G$ is an oracle for the gradient at
$w$. We do not mandate $G$ to be the full gradient of $\mathcal{L}$; it could,
for instance, correspond to the gradient $\nabla\mathcal{L}_{\mathcal{B}}$
with respect to a minibatch $\mathcal{B}$. Similarly, $w^{\star}$ is not
assumed to be a minimum of the objective function. Formally, for any gradient
oracle $G$, and any $w^{\star}\in\mathbb{R}^{d}$, $w\neq w^{\star}$:

$\textstyle\operatorname{RSI}(G,w,w^{\star}):=\frac{G(w)^{T}(w-w^{\star})}{\left\|w-w^{\star}\right\|_{2}^{2}}\quad\text{and}\quad\operatorname{EB}(G,w,w^{\star}):=\frac{\left\|G(w)\right\|_{2}}{\left\|w-w^{\star}\right\|_{2}}.$

The ratio between $\operatorname{RSI}$ and $\operatorname{EB}$ imparts a
direct geometrical interpretation:

$\textstyle\gamma(G,w,w^{\star}):=\frac{\operatorname{RSI}(G,w,w^{\star})}{\operatorname{EB}(G,w,w^{\star})}=\frac{G(w)^{T}(w-w^{\star})}{\left\|G\right\|_{2}\left\|w-w^{\star}\right\|_{2}}=cosine(G(w),w-w^{\star}),$

where $cosine(w_{1},w_{2})$ is the cosine of the angle between vectors $w_{1}$
and $w_{2}$.

This ratio, $\gamma$, signifies the alignment between the negative sampled
gradient and the direction from $w$ to $w^{\star}$. When $\gamma$ approaches
$1$, it indicates a negative gradient strongly directed toward $w^{\star}$.
Conversely, a $\gamma$ close to $0$ suggests a gradient almost orthogonal to
$w-w^{\star}$. A negative $\gamma$ indicates a negative gradient directed away
from $w^{\star}$. Additionally, $\gamma$ can be interpreted as the inverse of
a local variant of the condition number,
$\kappa:=\frac{\sup\operatorname{EB}}{\inf\operatorname{RSI}}$, which is a
measure of the complexity of optimizing $\mathcal{L}$ in prior works [15].

$\operatorname{RSI}$ and $\operatorname{EB}$ are intrinsically connected to
the dynamics of stochastic gradient descent (SGD). Indeed, the distance to
$w^{\star}$ following an SGD step with step size $\eta$ can be precisely
articulated using $\operatorname{RSI}$ and $\operatorname{EB}$. For all $w\neq
w^{\star},\mathcal{B}$,

$\displaystyle\left\|w-\eta\nabla\mathcal{L}_{\mathcal{B}}(w)-w^{\star}\right\|_{2}^{2}$
$\displaystyle=\left\|w-w^{\star}\right\|_{2}^{2}-2\eta\nabla\mathcal{L}_{\mathcal{B}}(w)^{T}(w-w^{\star})+\eta^{2}\left\|\nabla\mathcal{L}_{\mathcal{B}}(w)\right\|_{2}^{2}$
(4)
$\displaystyle=\left(1-2\eta\operatorname{RSI}\left(\nabla\mathcal{L}_{\mathcal{B}},w,w^{\star}\right)+\eta^{2}\operatorname{EB}^{2}\left(\nabla\mathcal{L}_{\mathcal{B}},w,,w^{\star}\right)\right)\|w-w^{\star}\|_{2}^{2}.$

Consequently, with a step size of

$\textstyle\eta^{\star}:=\underset{\eta}{\operatorname{argmin}}\left\|w-\eta\nabla\mathcal{L}_{\mathcal{B}}(w)-w^{\star}\right\|_{2}=\frac{\operatorname{RSI}(\nabla\mathcal{L}_{\mathcal{B}},w,w^{\star})}{\operatorname{EB}^{2}(\nabla\mathcal{L}_{\mathcal{B}},w,w^{\star})},$
(5)

SGD guarantees

$\textstyle\left\|w_{t+1}-w^{\star}\right\|_{2}=\sqrt{1-\gamma(\nabla\mathcal{L}_{\mathcal{B}},w,w^{\star})^{2}}\left\|w_{t}-w^{\star}\right\|_{2}.$
(6)

Furthermore, if
$\inf\limits_{w,\mathcal{B}}\operatorname{RSI}(\nabla\mathcal{L}_{\mathcal{B}},w,w^{\star})\geq\mu$
and
$\sup\limits_{w,\mathcal{B}}\operatorname{EB}(\nabla\mathcal{L}_{\mathcal{B}},w,w^{\star})\leq
L$ hold for some $\mu>0$, $L>0$, then equation (4) demonstrates that running
SGD with a fixed step size of $\eta=\frac{\mu}{L^{2}}$ will converge to
$w^{\star}$ at a guaranteed rate:

$\textstyle\left\|w_{t}-w^{\star}\right\|_{2}^{2}\leq(1-\frac{\mu^{2}}{L^{2}})\left\|w_{0}-w^{\star}\right\|_{2}^{2},$
(7)

This holds irrespective of how the minibatches are sampled. Under these
assumptions, this rate is, in fact, worst-case optimal among all continuous
first-order algorithms [16].

Experimental Measurement of RSI and EB: One of the most significant challenges
in experimentally measuring $\operatorname{RSI}$ and $\operatorname{EB}$ lies
in the selection of $w^{\star}$. Even in cases where the objective function
admits an unique global minimum, finding it in the context of deep neural
networks is computationally infeasible [3]. To navigate this complication, we
initially train a neural network and subsequently choose the final iterate
$w_{T}$ of the optimization sequence. Given successful training, the sequence
will converge to the vicinity of a (local) minimum, and measuring
$\operatorname{RSI}$ and $\operatorname{EB}$ with respect to this minimum will
provide insightful understanding of the training dynamics.

Notably, under this procedure, $w^{\star}$ is dependent on the optimization
sequence rather than being predetermined. Therefore, interpreting the ensuing
results warrants care, which we further discuss in Section 6.

Considering that saving all gradients and iterates observed during training
would be prohibitively resource-intensive, we perform two identical training
runs. The first run computes $w^{\star}$, and the second run computes
$\operatorname{RSI}$ and $\operatorname{EB}$ along the optimization path. A
detailed description of our experimental protocol is provided in Algorithm 1
in Appendix A.1, and we share our code at
https://github.com/Hiroki11x/LossLandscapeGeometry.

##  4 Empirical Geometry of Loss Landscapes Along Optimization Paths

Figure 2: Depicted are the trends of RSI (top), EB (middle) and $\gamma$
(bottom) across three different scenarios: image classification on CIFAR-10
with a ResNet-18 (left), image classification on ImageNet with a ResNet-50
(middle) and language modeling on WikiText-2 with a transformer model (right).

Figure 1 offers an initial glance at our results, outlining the behavior of
$\gamma$ across four datasets, with variations across architecture, batch
size, and optimization technique. Figure 2 presents a more streamlined view on
three of these datasets, exhibiting not only $\gamma$ but also
$\operatorname{RSI}$ and $\operatorname{EB}$ on a single run to preserve
clarity. To avoid precision issues when $w_{t}$ approaches $w^{\star}$, the
results from the final epoch have been excluded. Our hyperparameters were
initially adjusted to optimize validation accuracy, echoing practical
conditions. All experiments were coded in PyTorch [36] and detailed
descriptions of the specific training configurations, along with final test
performances, are available in Appendix A to ensure full reproducibility.

CIFAR-10 (ResNet-18): Across the entire training run, not a single iteration
exhibits a negative $\gamma$ (or equivalently $\operatorname{RSI}$). Even
though there are slight fluctuations across epochs, $\gamma$ predominantly
remains within the $[0.0075,0.02]$ range and does not exhibit substantial
shifts (with the exception of the initial epoch). While the variance of
$\operatorname{RSI}$ and $\operatorname{EB}$ across iterations tends to
increase as training progresses, their mean values largely remain stable.

ImageNet-1K (ResNet-50): Contrary to the CIFAR-10 case, there are few
iterations where $\gamma$ is negative, during the first epoch and towards the
end of training. However, these instances are exceedingly rare, and $\gamma$
exceeds $0.0018$ for the majority of the training period. Moreover, the
variance across iterations remains notably low until the later stages of
training. We observe that $\operatorname{RSI}$, $\operatorname{EB}$, and
$\gamma$ increase monotonically, with a sharp rise observed towards the end.

WikiText-2 (Transformer): Throughout the training, $\gamma$ remains strictly
positive and exceeds $0.05$ following the second epoch. The cosine similarity
maintains a remarkable stability, exhibiting only minor variations across
iterations and epochs. While $\operatorname{RSI}$ and $\operatorname{EB}$ show
very low variance across iterations, they do increase towards the end of the
training period.

###  4.1 Fundamental properties

Interpolation Regime: To accurately interpret the observations from the
experiments, it is crucial to differentiate between two distinct scenarios -
interpolation and non-interpolation. In the interpolation setting, the model
successfully reduces the loss to near zero by interpolating all training data
simultaneously. As a result, the sampled gradients invariably converge to zero
as the sequence approaches its final iterates, irrespective of the minibatch.
This consistent behavior allows $\operatorname{RSI}$ and $\operatorname{EB}$
to remain stable, as exemplified in the CIFAR-10 experiment (left column in
Figure 2).

Non-Interpolation Regime: In contrast, under the non-interpolation setting,
the model does not fit all training data but rather navigates within a low-
loss basin where $\nabla\mathcal{L}(w)$ is small, but stochastic gradients
remain significant. In such a scenario, $\operatorname{EB}$ inevitably rises
to infinity as $w_{t}-w^{\star}$ approaches zero. Similarly, unless the cosine
similarity reduces to zero (which is improbable given that gradient-based
updates naturally correlate $w_{t}-w^{\star}$ with
$\nabla\mathcal{L}_{\mathcal{B}}(w_{t})$), $\operatorname{RSI}$ will also
invariably increase to infinity. This behavior is evident in the WikiText-2
and ImageNet experiments (refer to the middle and right columns in Figure 2).
The phenomenon is particularly pronounced in the ImageNet case due to the
decaying learning rate schedule: the negligible learning rate during the later
stages of training induces minuscule distances between $w_{t}$ and
$w^{\star}$, subsequently resulting in a substantial increase in
$\operatorname{RSI}$ and $\operatorname{EB}$ values, even several epochs
before the end of training. Additional experimental results supporting this
interpretation are provided in Appendix C.

Late Training Behavior: The results obtained towards the end of the training
should be interpreted with caution. Besides the previously described
phenomenon in the non-interpolation regime, the correlation between sampled
gradients and $w_{t}-w^{\star}$ increases as the sequence nears its
termination. For instance, in the case of vanilla gradient descent, the
relation $w_{T-1}-w_{T}=\eta\nabla\mathcal{L}_{\mathcal{B}_{T-1}}(w_{T-1})$
holds, which implies that the cosine similarity at the last iteration is
necessarily $\gamma_{T}=1$. Although we exclude results from the final epoch
to mitigate this effect, it is impossible to entirely eliminate it. Further
discussion on related implications can be found in Section 6.

Summary of Observations: Upon careful analysis, we find that the optimization
trajectories of deep neural networks exhibit the following characteristic
features:

  * •

The cosine similarity, $\gamma$, is almost always positive with remarkably few
exceptions.

  * •

$\gamma$ demonstrates notable stability across both epochs and iterations,
with few deviations apart from the phenomena previously discussed.

  * •

The values of $\operatorname{RSI}$ and $\operatorname{EB}$ follow predictable
trends, contingent upon whether the model adheres to an interpolation or a
non-interpolation regime.

These observations imply that, despite the well-documented non-convexity of
the loss landscapes associated with neural networks and the inherent
stochasticity introduced by minibatch sampling, the learning process of neural
networks remains remarkably consistent. The networks progress steadily towards
their destination throughout the training, with each stochastic gradient
contributing valuable information to reach the final model state. Essentially,
gradients always point toward the right direction, and training trajectories
never take a wrong turn when optimizing the loss function. We find these
observations to be particularly remarkable on ImageNet. Given the presence of
$1000$ semantic classes (exceeding the batch size) and in excess of 5000
minibatches per epoch, the consistence of the cosine similarity $\gamma$
throughout entire epochs seems surprising. This leads us to recognize
$\operatorname{RSI}$ and $\operatorname{EB}$ as powerful tools that
effectively capture the elusive simplicity of neural loss landscapes.

We further explore the impact of various factors and provide a more
comprehensive substantiation of our findings in Section 5. Following this, we
discuss the implications and potential limitations of our observations in
Section 6. We also discuss plausible causes in Appendix D.

##  5 Influence of Training Settings

Batch Size: the top right of Figure 1 delineates the cosine similarities
corresponding to batch sizes ranging from $32$ to $256$ on the WikiText-2
dataset. As a complementary experiment, Figure 6 in Appendix B portrays the
cosine similarities associated with batch sizes from $64$ to $512$ on the
CIFAR-10 dataset. The outcomes of both these experiments consistently reveal a
positive correlation between batch size and cosine similarity. This outcome is
foreseeable: for two minibatches $\mathcal{B}_{i}$ and $\mathcal{B}_{j}$, we
have

$\textstyle\operatorname{RSI}(\nabla\mathcal{L}_{\mathcal{B}_{i}}+\nabla\mathcal{L}_{\mathcal{B}_{j}})=\operatorname{RSI}(\nabla\mathcal{L}_{\mathcal{B}_{i}})+\operatorname{RSI}(\nabla\mathcal{L}_{\mathcal{B}_{j}}),\quad\operatorname{EB}(\nabla\mathcal{L}_{\mathcal{B}_{i}}+\nabla\mathcal{L}_{\mathcal{B}_{j}})\leq\operatorname{EB}(\nabla\mathcal{L}_{\mathcal{B}_{i}})+\operatorname{EB}(\nabla\mathcal{L}_{\mathcal{B}_{j}}).$

It should be noted that the selection of batch size not only affects the
measurement of RSI and EB, but it also influences the optimization trajectory
and the speed of convergence. Therefore, direct numerical comparisons across
different batch sizes ought to be interpreted with caution. Nonetheless, our
observations suggest that cosine similarities may scale with the square root
of the batch size.

Optimizer: Figure 1 (bottom left) illustrates the cosine similarity for three
distinct optimizers utilized on the CIFAR-10 dataset. Intriguingly, Adam
appears to result in lower cosine similarity values, albeit with reduced
variance. We hypothesize that Adam, by amplifying the effective step size
along directions with lower curvature, traverses further in flat dimensions,
thereby leading to a reduced alignment compared to SGD. This conjecture is
substantiated by Figure 12 in Appendix C, demonstrating that the journey
undertaken by Adam indeed surpasses that of SGD in terms of distance. Notably,
the employment of a momentum value of 0.9 with SGD does not significantly
impact the value of $\gamma$, compared to not using momentum. Prior works also
suggest that the optimization methods may affect the geometry of visited
regions [5].

Model Depth and Width: Our attention now turns to the impact of depth and
width on the geometric characteristics of the optimization trajectory, as
depicted in Figure 1 (top left). In this experiment, we trained ResNets of
varying depth — 18, 50, and 152 layers — with both standard and doubled width.
A salient observation is that an increase in depth slightly enhances the
cosine similarities, while an increase in width appears to have a
comparatively trivial impact. These findings could potentially shed light on
the prevalent trend in contemporary neural network designs favouring increased
depth over width [17].

##  6 Key Takeaways and Discussion

Geometrically Justified Learning Rate Schedules: As established in Equation
(5), we define the locally optimal learning rate (loLR) as the minimizer of
$\left\|w_{t}-\eta\nabla\mathcal{L}_{\mathcal{B}_{t}}-w^{\star}\right\|_{2}$,
$\eta^{\star}(w)=\frac{\operatorname{RSI}(w)}{\operatorname{EB}^{2}(w)}$.

Figure 3: Left panel: The locally optimal learning rate, derived as per
Equation (5), for various architectures implemented on the CIFAR-10 dataset.
Right panel: The locally optimal learning rate, similarly determined, across a
spectrum of batch sizes employed on the WikiText-2 dataset.

It is important to note, however, that $\eta^{\star}$ may not necessarily be
globally optimal. Indeed, certain methodologies may initiate slower but
accumulate more information, ultimately leading to faster convergence over a
large number of steps. Furthermore, as the measurement of $\operatorname{RSI}$
and $\operatorname{EB}$ requires the knowledge of $w^{\star}$, which in turn
depends on the learning rate (LR), the expression cannot be utilized to
dynamically tune it.

Despite these limitations, we find intriguing parallels between the evolution
of the loLR derived from our experiments and the shape of empirically
validated LR schedules, as demonstrated in Figure 3. For instance, a widely
adopted strategy for training on ImageNet involves a linear warm-up phase of
the LR for the initial few epochs, followed by a cosine annealing phase. This
pattern is mirrored in our empirical observations on ImageNet, except for a
sharper decrease immediately after warmup.

Moreover, the results on WikiText-2 echo two popular practices: linearly
decreasing the LR and increasing the batch size over time. These intriguing
observations suggest that the geometry of the loss landscape could potentially
inform the design of more effective learning rate schedules.

Lastly, the apparent correspondence between loLR and empirical learning rate
strategies implies that the efficiency of fixed learning rates may be
contingent upon the stationarity of $\operatorname{RSI}$ and
$\operatorname{EB}$. Similarly, the existence of straightforward and efficient
learning rate schedules can be associated with the predictable evolution of
these geometrical properties. This strongly reinforces the view that such
geometrical attributes play a substantial role in the widespread practical
successes of deep learning.

Biases Induced by Using Final Iterates as Reference Points: A critical
limitation of our experimental approach is the inescapable correlation between
$w^{\star}$ and the optimization sequence. This association must be thoroughly
addressed to appropriately interpret our findings.

Figure 4: Depiction of cosine similarities during the training of a ResNet-18
on the CIFAR-10 dataset, with variations in (left) initialization seed and
(right) epoch budget.

$\bullet$ Initialization: Firstly, $\operatorname{RSI}$ and
$\operatorname{EB}$ may represent local properties of the loss landscape, and
could be dependent on the initialization region. However, this possibility is
refuted by the left panel of Figure 4, which demonstrates minimal variation in
$\gamma$ measurements across different random seeds.

$\bullet$ Epoch Budget: Secondly, our results might be influenced by the
particular moment when we terminate the optimization sequence to extract
$w^{\star}$. The right panel of Figure 4 presents different measurements for
epoch budgets ranging from $100$ to $280$, with all other parameters kept
consistent. Our findings indicate a relative similarity in results before the
sequence nears $w^{\star}$, suggesting that our experiments do not display
excessive sensitivity to the epoch budget.

$\bullet$ Induced Bias: However, this experiment also underscores the
phenomenon detailed in Section 4.1: as the sequence approaches completion, the
correlation between sampled gradients and $w_{t}-w^{\star}$ \- induced by
gradient updates - becomes increasingly significant. This correlation is a by-
product of the optimization method, rather than a feature of local geometry,
and augments the value of $\operatorname{RSI}$ and $\gamma$ by diminishing the
impact of stochasticity. Consequently, this correlation should be taken into
account when interpreting $\operatorname{RSI}$ and $\operatorname{EB}$ in the
concluding epochs.

A compelling illustration of this correlation can be seen in a discrete
isotropic random walk with a fixed step size $s$ in a dimension $d$. When
dimension $d$ significantly exceeds the number of steps, each pair of steps
can be assumed to be nearly orthogonal with high probability. In such a
setting, if we denote $(x_{t})_{t=0\dots T}$ as the sequence generated by the
random walk, we can calculate that, with high probability, $\forall t$,

$\frac{(x_{t}-x_{t+1})^{T}(x_{t}-x_{T})}{\|x_{t}-x_{T}\|_{2}^{2}}\approx\frac{\|x_{t}-x_{t+1}\|_{2}^{2}}{\|x_{t}-x_{T}\|_{2}^{2}}\approx\frac{1}{T-t}>0\quad\text{and}\quad\frac{\left\|x_{t}-x_{t+1}\right\|_{2}}{\left\|x_{t}-x_{T}\right\|_{2}}\approx\frac{1}{\sqrt{T-t}}$
(8)

Consequently, the cosine similarity $\gamma(x_{t})\approx(T-t)^{-0.5}$ remains
strictly positive, and experiences a sharp increase toward the end,
exemplifying the effect of the correlation induced by the selection of
$w^{\star}$. It’s worth noting that in the case of neural networks, $\gamma$
remains approximately constant for the majority of training (as is clearly
visible in Figure 1), which marks a distinction in their dynamics.
Nonetheless, akin to the random walk scenario, it can be anticipated that the
correlation induced by the choice of $w^{\star}$ would become increasingly
evident as the number of remaining iterations diminishes.

Contrasting Examples: Functions Without Beneficial Geometric Properties: We
now turn our attention to delineating the behaviors that could potentially
manifest in stochastic and non-convex optimization scenarios. To this end, we
have engineered two illustrative counter-examples which effectively
demonstrate that the consistency observed in Sections 4 and 5 is not a mere
byproduct of our experimental paradigm.

Figure 5: Left column: $\operatorname{RSI}$ and $\gamma$ values for a convex
yet significantly stochastic objective. Right column: $\operatorname{RSI}$ and
$\gamma$ values for a deterministic objective characterized by substantial
non-convexity. Despite their simplicity, these functions exemplify the
irregular behaviors one might anticipate encountering within the complex
terrain of neural loss landscapes.

Our first example, termed Asymmetric Linear Model (ALM), entails the training
of a linear model with the objective of consistently yielding outputs that are
lower than their corresponding targets. The error between these values is
calculated on stochastic minibatches using Root Mean Square Error (RMSE),
thereby introducing a substantial degree of stochasticity. Despite this, the
objective is a finite sum of convex functions and thus remains convex.

The second function, designated Sinusoidal Mixture (SM), is deterministic but
exhibits a pronounced degree of non-convexity. The mathematical expressions
for both ALM and SM are presented below, with coefficients $a_{i},x_{i},y_{i}$
drawn randomly from normal distributions,

$ALM(w)=\sum_{i}\left[max(0,w^{T}x_{i}-y_{i})\right]^{2};\quad
SM(w)=\left\|w\right\|_{2}^{2}+100\sum_{i}\sin(a_{i}w_{i})^{2}.$ (9)

Figure 5 presents the measurements of $\operatorname{RSI}$ and $\gamma$ for
both ALM and SM. Although these functions are characterized by relatively
simple functional forms and do not simultaneously exhibit stochasticity and
non-convexity, they demonstrate unpredictable trajectories and negative values
for $\operatorname{RSI}$ and $\gamma$. This evidence compellingly suggests
that the observed simplicity associated with neural networks is not a trivial
characteristic.

##  7 Conclusion

We have conducted an extensive series of experiments, assessing
$\operatorname{RSI}$ and $\operatorname{EB}$ across a broad spectrum of
training settings. These experiments reveal that these geometric properties
display a collection of desirable characteristics, effectively demonstrating
that neural network training proceeds smoothly, maintaining a consistently
steady advancement towards its destination throughout the training process.

These results contrast starkly with the theoretical complexity of neural
landscapes and potentially open new pathways for developing theoretical
results tailored to deep learning, or for designing optimization algorithms
that exploit the geometry of empirical objective functions.

A noteworthy point is that while $\operatorname{RSI}$ and $\operatorname{EB}$
appear to encapsulate significant beneficial aspects of neural networks, they
likely do not encompass the entire scope of these advantages. There may be
additional, complementary properties yet to be discovered. An intriguing
indication of this is the fact that vanilla gradient descent has been proven
to be exactly optimal for functions verifying the lower restricted secant
inequality and upper error bound [16]. Given the well-documented efficacy of
momentum in training neural networks, we conjecture that momentum exploits
additional properties not captured by $\operatorname{RSI}$ and
$\operatorname{EB}$, which we encourage future works to explore.

## Acknowledgments and Disclosure of Funding

The authors would like to extend special thanks to Leonard Boussioux, Damien
Scieur and Baptiste Goujaud, for thoughtful discussions and useful feedback.
Ioannis Mitliagkas acknowledges support by an NSERC Discovery grant
(RGPIN-2019-06512), a Samsung grant and a Canada CIFAR AI chair.

The Vaihingen data set was provided by the German Society for Photogrammetry,
Remote Sensing and Geoinformation (DGPF)[6]: http://www.ifp.uni-
stuttgart.de/dgpf/DKEP-Allg.html.

## References

  * Audebert et al. [2017] N. Audebert, B. L. Saux, and S. Lefèvre.  Beyond rgb: Very high resolution urban remote sensing with multimodal deep networks.  _ISPRS Journal of Photogrammetry and Remote Sensing_ , 2017.  ISSN 0924-2716.  doi: https://doi.org/10.1016/j.isprsjprs.2017.11.011.
  * Badrinarayanan et al. [2017] V. Badrinarayanan, A. Kendall, and R. Cipolla.  Segnet: A deep convolutional encoder-decoder architecture for image segmentation.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 39(12):2481–2495, 2017.  doi: 10.1109/TPAMI.2016.2644615.
  * Blum and Rivest [1992] A. L. Blum and R. L. Rivest.  Training a 3-node neural network is np-complete.  _Neural Networks_ , 5(1):117–127, 1992.  ISSN 0893-6080.  doi: https://doi.org/10.1016/S0893-6080(05)80010-3.  URL https://www.sciencedirect.com/science/article/pii/S0893608005800103.
  * Chizat et al. [2019] L. Chizat, E. Oyallon, and F. Bach.  On lazy training in differentiable programming.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper_files/paper/2019/file/ae614c557843b1df326cb29c57225459-Paper.pdf.
  * Cohen et al. [2021] J. M. Cohen, S. Kaur, Y. Li, J. Z. Kolter, and A. Talwalkar.  Gradient descent on neural networks typically occurs at the edge of stability.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021.  URL https://openreview.net/forum?id=jh-rTtvkGeM.
  * Cramer and Haala [2010] M. Cramer and N. Haala.  Dgpf project: Evaluation of digital photogrammetric aerial-based imaging systems- overview and results from the pilot center.  _Photogrammetric engineering and remote sensing_ , 76(9):1019–1029, 2010.
  * Deng et al. [2009] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 248–255, 2009.  doi: 10.1109/CVPR.2009.5206848.
  * Dinh et al. [2017] L. Dinh, R. Pascanu, S. Bengio, and Y. Bengio.  Sharp minima can generalize for deep nets.  In _International Conference on Machine Learning_ , pages 1019–1028. PMLR, 2017.
  * Dmitriy Drusvyatskiy [2018] A. S. L. Dmitriy Drusvyatskiy.  Error bounds, quadratic growth, and linear convergence of proximal methods.  In _Mathematics of Operations Research 43(3):919-948_ , 2018.  URL https://doi.org/10.1287/moor.2017.0889.
  * Fatras et al. [2021] K. Fatras, B. B. Damodaran, S. Lobry, R. Flamary, D. Tuia, and N. Courty.  Wasserstein Adversarial Regularization for learning with label noise.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2021.
  * Fort et al. [2020] S. Fort, G. K. Dziugaite, M. Paul, S. Kharaghani, D. M. Roy, and S. Ganguli.  Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the neural tangent kernel.  In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 5850–5861. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper_files/paper/2020/file/405075699f065e43581f27d67bb68478-Paper.pdf.
  * Frankle et al. [2020] J. Frankle, G. K. Dziugaite, D. M. Roy, and M. Carbin.  Linear mode connectivity and the lottery ticket hypothesis.  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 3259–3269. PMLR, 2020\.  URL http://proceedings.mlr.press/v119/frankle20a.html.
  * Garipov et al. [2018] T. Garipov, P. Izmailov, D. Podoprikhin, D. P. Vetrov, and A. G. Wilson.  Loss surfaces, mode connectivity, and fast ensembling of dnns.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper_files/paper/2018/file/be3087e74e9100d4bc4c6268cdbe8456-Paper.pdf.
  * Goodfellow et al. [2015] I. Goodfellow, O. Vinyals, and A. Saxe.  Qualitatively characterizing neural network optimization problems.  In _International Conference on Learning Representations_ , 2015.  URL http://arxiv.org/abs/1412.6544.
  * Guille-Escuret et al. [2021] C. Guille-Escuret, M. Girotti, B. Goujaud, and I. Mitliagkas.  A study of condition numbers for first-order optimization.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1261–1269. PMLR, 2021.
  * Guille-Escuret et al. [2022] C. Guille-Escuret, A. Ibrahim, B. Goujaud, and I. Mitliagkas.  Gradient descent is optimal under lower restricted secant inequality and upper error bound.  In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=s1yaWFDLxVG.
  * He et al. [2016] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 770–778, 2016.  doi: 10.1109/CVPR.2016.90.
  * Ioffe and Szegedy [2015a] S. Ioffe and C. Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In F. Bach and D. Blei, editors, _Proceedings of the 32nd International Conference on Machine Learning_ , volume 37 of _Proceedings of Machine Learning Research_ , pages 448–456, Lille, France, 07–09 Jul 2015a. PMLR.  URL https://proceedings.mlr.press/v37/ioffe15.html.
  * Ioffe and Szegedy [2015b] S. Ioffe and C. Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In _International conference on machine learning_ , pages 448–456. pmlr, 2015b.
  * Jacot et al. [2018] A. Jacot, F. Gabriel, and C. Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper_files/paper/2018/file/5a4be1fa34e62bb8a6ec6b91d2462f5a-Paper.pdf.
  * Jin et al. [2019] C. Jin, P. Netrapalli, R. Ge, S. M. Kakade, and M. I. Jordan.  On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points, 2019.
  * Karimi et al. [2016] H. Karimi, J. Nutini, and M. Schmidt.  Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition.  In P. Frasconi, N. Landwehr, G. Manco, and J. Vreeken, editors, _Machine Learning and Knowledge Discovery in Databases_ , volume abs/1608.04636, pages 795–811, Cham, 2016. Springer International Publishing.
  * Kingma and Ba [2017] D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization, 2017.
  * Krizhevsky [2014] A. Krizhevsky.  One weird trick for parallelizing convolutional neural networks.  _arXiv preprint arXiv:1404.5997_ , 2014.
  * Krizhevsky et al. [2012] A. Krizhevsky, V. Nair, and G. Hinton.  Learning multiple layers of features from tiny images.  _Advances in Neural Information Processing Systems_ , 2012.  URL http://www.cs.toronto.edu/~kriz/cifar.html.
  * Lee et al. [2019] J. Lee, L. Xiao, S. S. Schoenholz, Y. Bahri, R. Novak, J. Sohl-Dickstein, and J. Pennington.  Wide neural networks of any depth evolve as linear models under gradient descent.  _arXiv preprint arXiv:1902.06720_ , 2019.
  * Li et al. [2018] H. Li, Z. Xu, G. Taylor, C. Studer, and T. Goldstein.  Visualizing the loss landscape of neural nets.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper_files/paper/2018/file/a41b3bb3e6b050b6c9067c67f663b915-Paper.pdf.
  * Liu et al. [2022] C. Liu, L. Zhu, and M. Belkin.  Loss landscapes and optimization in over-parameterized non-linear systems and neural networks.  _Applied and Computational Harmonic Analysis_ , 59:85–116, 2022.  ISSN 1063-5203.  doi: https://doi.org/10.1016/j.acha.2021.12.009.  URL https://www.sciencedirect.com/science/article/pii/S106352032100110X.  Special Issue on Harmonic Analysis and Machine Learning.
  * Logan et al. [2019] R. L. Logan, IV, N. F. Liu, M. E. Peters, M. Gardner, and S. Singh.  Barack’s wife Hillary: Using knowledge graphs for fact-aware language modeling.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , Florence, Italy, July 2019\. Association for Computational Linguistics.
  * Loizou et al. [2021] N. Loizou, S. Vaswani, I. H. Laradji, and S. Lacoste-Julien.  Stochastic polyak step-size for SGD: an adaptive learning rate for fast convergence.  In A. Banerjee and K. Fukumizu, editors, _The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event_ , volume 130 of _Proceedings of Machine Learning Research_ , pages 1306–1314. PMLR, 2021.  URL http://proceedings.mlr.press/v130/loizou21a.html.
  * Lucas et al. [2021] J. Lucas, J. Bae, M. R. Zhang, S. Fort, R. S. Zemel, and R. B. Grosse.  Analyzing monotonic linear interpolation in neural network loss landscapes.  _CoRR_ , abs/2104.11044, 2021.  URL https://arxiv.org/abs/2104.11044.
  * Luo and Tseng [1993] Z.-Q. Luo and P. Tseng.  Error bounds and convergence analysis of feasible descent methods: a general approach.  _Annals of Operations Research_ , 46(1):157–178, 1993.
  * Merity et al. [2016] S. Merity, C. Xiong, J. Bradbury, and R. Socher.  Pointer sentinel mixture models, 2016.
  * Nguyen et al. [2018] L. M. Nguyen, P. H. Nguyen, M. van Dijk, P. Richtárik, K. Scheinberg, and M. Takác.  SGD and hogwild! convergence without the bounded gradients assumption.  In J. G. Dy and A. Krause, editors, _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 3747–3755. PMLR, 2018\.  URL http://proceedings.mlr.press/v80/nguyen18c.html.
  * Panageas et al. [2019] I. Panageas, G. Piliouras, and X. Wang.  First-order methods almost always avoid saddle points: The case of vanishing step-sizes.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper_files/paper/2019/file/3fb04953d95a94367bb133f862402bce-Paper.pdf.
  * Paszke et al. [2019] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Köpf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala.  Pytorch: An imperative style, high-performance deep learning library, 2019\.
  * Qian et al. [2019] X. Qian, P. Richtárik, R. M. Gower, A. Sailanbayev, N. Loizou, and E. Shulgin.  SGD with arbitrary sampling: General analysis and improved rates.  In K. Chaudhuri and R. Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 5200–5209. PMLR, 2019.  URL http://proceedings.mlr.press/v97/qian19b.html.
  * Qian et al. [2023] Y. Qian, S. Pan, and L. Xiao.  Error bound and exact penalty method for optimization problems with nonnegative orthogonal constraint.  _IMA Journal of Numerical Analysis_ , 02 2023.  ISSN 0272-4979.  doi: 10.1093/imanum/drac084.  URL https://doi.org/10.1093/imanum/drac084.  drac084.
  * Ronneberger et al. [2015] O. Ronneberger, P. Fischer, and T. Brox.  U-net: Convolutional networks for biomedical image segmentation.  In _The International Conference on Medical image computing and computer-assisted intervention_ , 2015.
  * Rottensteiner et al. [2012] F. Rottensteiner, G. Sohn, J. Jung, M. Gerke, C. Baillard, S. Benitez, and U. Breitkopf.  The ISPRS benchmark on urban object classification and 3D building reconstruction.  _ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences_ , 2012.
  * Santurkar et al. [2018a] S. Santurkar, D. Tsipras, A. Ilyas, and A. Madry.  How does batch normalization help optimization?  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018a.  URL https://proceedings.neurips.cc/paper_files/paper/2018/file/905056c1ac1dad141560467e0a99e1cf-Paper.pdf.
  * Santurkar et al. [2018b] S. Santurkar, D. Tsipras, A. Ilyas, and A. Madry.  How does batch normalization help optimization?  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018b.  URL https://proceedings.neurips.cc/paper_files/paper/2018/file/905056c1ac1dad141560467e0a99e1cf-Paper.pdf.
  * Schöpfer [2016] F. Schöpfer.  Linear convergence of descent methods for the unconstrained minimization of restricted strongly convex functions.  _SIAM J. Optim._ , 26:1883–1911, 2016.
  * Shamir and Zhang [2013] O. Shamir and T. Zhang.  Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes.  In _Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013_ , volume 28 of _JMLR Workshop and Conference Proceedings_ , pages 71–79. JMLR.org, 2013\.  URL http://proceedings.mlr.press/v28/shamir13.html.
  * Vaswani et al. [2017] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. u. Kaiser, and I. Polosukhin.  Attention is all you need.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper_files/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf.
  * Yi et al. [2019] X. Yi, S. Zhang, T. Yang, K. H. Johansson, and T. Chai.  Exponential convergence for distributed smooth optimization under the restricted secant inequality condition, 2019.
  * Yuan et al. [2016] K. Yuan, Q. Ling, and W. Yin.  On the convergence of decentralized gradient descent.  _SIAM J. Optim._ , 26:1835–1854, 2016.
  * Zhang and Yin [2013] H. Zhang and W. Yin.  Gradient methods for convex minimization: better rates under weaker conditions.  Cam report, UCLA, 2013.
  * Zhou and So [2015] Z. Zhou and A. So.  A unified approach to error bounds for structured convex optimization problems.  _Mathematical Programming_ , 12 2015.  doi: 10.1007/s10107-016-1100-9.

##  Appendix A Experimental Setting

###  A.1 Algorithm

Algorithm A.1 provides a detailed account of our experimental protocol. This
algorithm describes our methodology to measure $\operatorname{RSI}$ and
$\operatorname{EB}$ values throughout the training process.

Intuitively, the algorithm follows two training runs with identical
initialization and minibatch sampling. The first runs aims at computing the
last iterate $w^{\star}$ and saving it, and the second runs uses $w^{\star}$
to compute $\operatorname{RSI}$ and $\operatorname{EB}$.

This approach removes the necessity to save all gradients throughout the run
(in order to compute $\operatorname{RSI}$ and $\operatorname{EB}$ at the end),
which would be unreasonably expensive in memory.

Algorithm 1 Measurement of $\operatorname{RSI}$ and $\operatorname{EB}$

Input: initial weights $w_{0}$, sequence of minibatches $\mathcal{B}_{0\dots
T-1}$

1: for $t=0,\dots,T-1$ do

2: compute gradient $G_{t}=\nabla\mathcal{L}_{\mathcal{B}_{t}}(w_{t})$

3: update weights $w_{t+1}=Opt(w_{0\dots t},G_{0\dots t}))$

4: end for

5: $w^{\star}\leftarrow w_{T}$

6: reset weights to $w_{0}$

7: for $t=0,\dots,T-1$ do

8: compute gradient $G_{t}=\nabla\mathcal{L}_{\mathcal{B}_{t}}(w_{t})$

9: compute
$RSI_{t}=\frac{G_{t}^{T}(w_{t}-w^{\star})}{\|w_{t}-w^{\star}\|_{2}^{2}}$

10: compute $EB_{t}=\frac{\|G_{t}\|_{2}}{\|w_{t}-w^{\star}\|_{2}}$

11: update weights $w_{t+1}=Opt(w_{0\dots t},G_{0\dots t}))$

12: end for

Output: $RSI_{0\dots T-1}$, $EB_{0\dots T-1}$

###  A.2 Implementation and Environment for Experiments

Computational Environment: We perform our experiments mainly with cluster A
(redacted until publication). For cluster A, each node is composed of NVIDIA
A100$\times$4GPU and AMD Milan 7413 @ 2.65 GHz 128M cache L3$\times$2CPU. As a
software environment, we use Rocky Linux 8.7, gcc 9.3.0, Python 3.10.2,
pytorch 1.13.1, torchvision 0.14.1, cuDNN 8.2.0, and CUDA 11.4.

Licence of Datasets: It should be noted that the CIFAR-10 dataset [25] does
not explicitly stipulate any licensing terms
111https://www.cs.toronto.edu/~kriz/cifar.html. The authors of the CIFAR-10
merely ask users of their dataset to provide appropriate citation. ImageNet-1K
[7] does not explicitly state its license 222https://www.image-
net.org/challenges/LSVRC/2012/index.php. Licenses of the WikiText-2 [29] is
CC-BY-SA-3.0 333https://www.salesforce.com/products/einstein/ai-research/the-
wikitext-dependency-language-modeling-dataset/. No license is specified for
the dataset in Vaihingen [6], but it is allowed to be used in scientific
papers. However, acknowledgment and citation are required444For more details,
see page 7 of
https://www2.isprs.org/media/komfssn5/complexscenes_revision_v4.pdf.

Implementation: All codes for experiments are modifications of the codes
provided by PyTorch’s official implementation for image classification and
language modeling tasks555https://github.com/pytorch/examples and Audebert et
al. [1] for segmentation task 666https://github.com/nshaud/DeepNetsForEO. The
license for the official Pytorch implementation is the BSD-3-Clause, and the
license for the segmentation task implementation is GPLv3. Our code can be
found at the link below.
https://github.com/Hiroki11x/LossLandscapeGeometry

###  A.3 Datasets description

CIFAR10: CIFAR-10 dataset [25], one of the most widely used datasets for
machine learning research, is a unique resource that offers a robust benchmark
for algorithms, primarily image recognition. The dataset is a curated
collection of 60,000 color images, each of a size of 32x32 pixels, uniformly
divided across ten distinctive classes. These classes encompass various common
objects: airplanes, automobiles, birds, cats, deer, dogs, frogs, horses,
ships, and trucks. Each class in the CIFAR-10 dataset is represented equally,
with 6,000 images per category. The dataset is split into two segments: a
training set comprising 50,000 images and a test set of 10,000 images.

ImageNet-1K: The ImageNet-1K dataset, a subset of the more extensive ImageNet
database [7], has become an essential resource for research in machine
learning, particularly for image recognition and classification tasks.
ImageNet-1K is an extensively curated dataset of approximately 1.28 million
high-resolution color images spread across 1,000 distinct categories or
classes. These classes span various objects, organisms, and phenomena,
capturing a rich diversity of the visual world.

WikiText-2: The WikiText-2 dataset [29] is a significant benchmark for various
natural language processing tasks, specifically those related to language
modeling. It comprises over 2 million tokens extracted from verified Wikipedia
articles. WikiText-2 retains the original structure and complexity of the
language found in the source articles. This characteristic has enabled
training models to handle various language structures and styles. The dataset
is divided into three segments: a training set with roughly 2.08 million
tokens, a validation set with approximately 217,000 tokens, and a test set
with about 245,000 tokens.

Vaihingen: The Vaihingen dataset [40] is a land covering remote sensing
dataset. Its purpose is to segment correctly aerial images of the Vaihingen
city in Germany. It is composed of 33 tiles and we use 11 tiles for training,
5 tiles for validation, and the remaining 17 tiles for testing our model,
which is the split used in [10]. Furthermore, we only consider the RGB
components of the Vaihingen dataset. We follow the training procedure and
PyTorch implementation from [1]. We build our training (resp. validation)
dataset by taking randomly $256\times 256$ patches from the training (resp.
validation) tiles. The number of images seen during a training epoch is set to
10.000 patches while it is set to 1000 for the validation set.

Table 1: Default setting of experiments

Task | Dataset | Model | Batch size | Epochs
---|---|---|---|---
Image Classification | CIFAR-10 | ResNet18-1 | [64, 128, 256, 512] | [100, 190, 280]
Medium-MLP | [64, 128, 256, 512] | [100, 190, 280]
ImageNet-1K | ResNet-18-1 | 256 | [90, 180]
ResNet-18-2 | 256 | [90, 180]
ResNet-50-1 | 256 | [90, 180]
ResNet-50-2 | 256 | [90, 180]
ResNet-152-0.5 | 256 | [90, 180]
ResNet-152-1 | 256 | [90, 180]
Word Language Model | WikiText-2 | Transformer | [32, 64, 128, 256] | 20
Segmentation | Vaihingen | UNet | 10 | 26
SegNet | 10 | 26

###  A.4 Hyperparameters and Detailed Configurations

In the experimental procedure of our study, we employed a systematic grid
search method to explore hyperparameters. This approach facilitates the
identification of the most effective combinations that provide superior
performance.

The specifics concerning the batch size and the total number of epochs
allocated for each dataset and corresponding model have been exhaustively
tabulated in Table 1. These parameters were meticulously selected to ensure
optimal learning while mitigating overfitting concerns.

Further, we present detailed settings of specific ablation experiments in
Table 2, 3,4, and 5. These ranges were defined based on prior search of
hyperparameters maximizing validation performance.

’SGD’ denotes the standard SGD algorithm without momentum, ’Momentum’ denotes
SGD with momentum with $\beta=0.9$, and ’Adam’ denotes the Adam algorithm with
$\beta_{1}=0.9$ and $\beta_{2}=0.999$.

CIFAR10: We train a ResNet-18 [17] for $190$ epochs on CIFAR-10 [25] with SGD
+ momentum using a batch size of $256$, a weight decay of $10^{-6}$, and a
fixed step size of $10^{-2}$ as a default configuration.

For batch-size experiments, the learning rate was designated as $5.0\times
10^{-3}$ for a batch size of $64$, and subsequently scaled proportionally to
the square root of the batch size, adhering to the guidelines from prior
research [24].

ImageNet-1K: We train a ResNet-50 on ImageNet [7] for $180$ epochs with SGD +
momentum using a batch size of $256$, weight decay of $10^{-4}$, and a
learning rate of $10^{-3}$. The learning rate is subjected to a linear warmup
for the first $3$ epochs, followed by cosine annealing as a default
configuration. We indicate by ’max LR’ the maximum value of the learning rate,
reached after the warmup epochs.

WikiText-2: We train a transformer [45] 777We use pytorch official
implementation of transformer for language model:
https://github.com/pytorch/examples/blob/main/word_language_model/model.py on
WikiText-2 [33] for $20$ epochs with Adam [23] using a batch size of $32$,
weight decay of $10^{-5}$ and learning rate of $10^{-4}$.

Vaihingen: We train a SegNet [2] and a UNet [39]. We augment our data with
flip and mirror transformations. We use a batch size of $10$ patches taken
randomly within images as done in [1]. We train for $25$ epochs with SGD +
momentum, learning rate $0.01$ and weight decay $1e^{-5}$. We then do an extra
epoch with the learning rate and the weight decay divided by 10. Note that we
train both the UNet and the SegNet from _scratch_.

Table 2: Hyperparameter: Image Classification Task (CIFAR-10)

Task | Model | Dataset | Optimizer | Batch size | LR | Epochs Budget
---|---|---|---|---|---|---
Optimizer | ResNet18-1 | CIFAR-10 |  | [SGD,
---
Momentum,
Adam]
256 |  | [0.0001,
---
0.0005,
0.001]
[100, 190, 280]
Seed | ResNet18-1 | CIFAR-10 | Momentum | 256 | 0.01 | 190
Batch Size | ResNet18-1 | CIFAR-10 | Momentum | [64, 128, 256, 512] | 0.005 888The base learning rate is configured with an assumption of a batch size of 64. If the batch size is doubled, the learning rate should be multiplied by the square root of 2. | 190
Model |  | [Medium-MLP,
---
ResNet18-2]
CIFAR-10 | Momentum | 256 | 0.01 | 150

Table 3: Hyperparameter: Image Classification Task (ImageNet-1K)

Task | Model | Dataset | Optimizer | Batch size | max LR | Epochs Budget
---|---|---|---|---|---|---
Model |  | [ResNet18-1,
---
ResNet18-2,
ResNet50-1,
ResNet50-2,
ResNet152-05,
ResNet152-1]
ImageNet-1K | Momentum | 256 | 0.1 | [90, 180]

88footnotetext: Same as above. Table 4: Hyperparameter: Language Model Task
(WikiText-2)

Task | Model | Dataset | Optimizer | Batch size | LR | Epochs Budget
---|---|---|---|---|---|---
Batch Size | Transformer | WikiText-2 | Adam | [32, 64, 128, 256] | 0.0001 999Same as above. | 20

Table 5: Hyperparameter: Segmentation Task (Vaihingen)

Task | Model | Dataset | Optimizer | Batch size | LR | Epochs Budget
---|---|---|---|---|---|---
Model | [UNet, SegNet] | Vaihingen | Momentum | 10 | 0.01 | 26

###  A.5 Validation performance

To support the relevance of our experimental setting, we report the validation
performance in the standard settings of each dataset and model.

Table 6: Validation accuracy on CIFAR-10 with batch size 256. Model | Validation accuracy
---|---
ResNet18-1 | 90.25
Vanilla MLP | 59.42
Table 7: Validation accuracy on ImageNet with batch size 256. Model | Validation accuracy
---|---
ResNet18-1 | 67.63
ResNet18-2 | 69.75
ResNet50-1 | 72.31
ResNet50-2 | 73.67
ResNet152-0.5 | 72.23
ResNet152-1 | 73.07
Table 8: Validation perplexity on WikiText-2 with batch size 64. Model | Validation perplexity
---|---
Transformer | 60.72
Table 9: Validation accuracy on Vaihingen with batch size 10. Model | Validation accuracy
---|---
SegNet | 84.56
UNet | 85.40

##  Appendix B Ablation Study

In this section, we provide additional results that did not fit in the main
paper for ablation studies. For instance, in addition to the cosine
similarities presented in figure 1, we provide the individual values of
$\operatorname{RSI}$ and $\operatorname{EB}$.

We provide in Figure 6 the cosine similarities for different batch sizes on
CIFAR-10, as a complement to Figure 1 to study the impact of batch size
$\operatorname{RSI}$ and $\operatorname{EB}$.

Figure 6: cosine similarities measured during the training of a ResNet-18 on
CIFAR-10, for batchsizes ranging from $64$ to $512$. Figure 7:
$\operatorname{RSI}$ and $\operatorname{EB}$ throughout training of a
transformer on WikiText-2 with different batch sizes. This figure is
complementary to figure 1. Figure 8: $\operatorname{RSI}$ and
$\operatorname{EB}$ throughout training for the training of a ResNet18 on
CIFAR-10 with different optimizers. This figure is complementary to figure 1.
Figure 9: $\operatorname{RSI}$ and $\operatorname{EB}$ throughout training for
the training of different ResNet architectures on ImageNet. This figure is
complementary to figure 1. Figure 10: $\operatorname{RSI}$ and
$\operatorname{EB}$ throughout training for the training of a ResNet18 on
ImageNet with different random seed. This figure is complementary to figure 4.
Figure 11: $\operatorname{RSI}$ and $\operatorname{EB}$ throughout training
for two different architectures on Vaihingen semantic segmentation. This
figure is complementary to figure 1.

##  Appendix C Additional figures

In this section we introduce additional figure supporting claims or
conjectures made in the main paper.

Figure 12 shows the evolution of $\|w_{t}-w^{\star}\|_{2}$ throughout
training. We can see Adam traverses a larger distance than Vanilla SGD and
Momentum SGD, and evolves as a more regular pace. We believe this could be a
factor in the lower cosine similarities exhibited by Adam in Figure 1.

Figure 12: $\|w_{t}-w^{\star}\|_{2}$ over training of a ResNet18-1 on
CIFAR-10, with different optimizers.

Figure 13 indicates the value of $\|w_{t}-w^{\star}\|_{2}$ over training in
the three settings of Figure 2. An important remark is that due to the cosine
decreasing learning rate schedule, in the case of ImageNet, this distance
becomes negligible in the last 25 epochs. This raise precision issues as
discussed in section 4.1. Since $w_{t}$ is subject to negligible variations in
the last $25$ epochs of the ImageNet experiment, Figures 1 and Figure 2 omit
the epochs after 155 in the case of ImageNet, in order to improve readability
and focus on meaningful settings.

Figure 13: $\|w_{t}-w^{\star}\|_{2}$ over training in the three different
settings of Figure 2.

##  Appendix D Plausible causes

In this section, we examine potential factors that might be contributing to
the remarkable geometric regularity observed via $\operatorname{RSI}$ and
$\operatorname{EB}$ within the loss landscapes of neural networks. These are
conjectural in nature, and we advocate for more rigorous investigation in
future work to substantiate these propositions.

$\bullet$ Architectural Characteristics: The deep learning landscape has
witnessed a plethora of architectural enhancements since its inception.
Notably, ResNets incorporate advanced features such as skip-connections and
batch normalization [19], which were found to simplify the structure of the
loss landscape [41, 27]. It is plausible that such favorable geometric
attributes could play a significant role in the success of neural network
architectures. Therefore, our observations may be more a byproduct of the
selection of high-performing networks rather than an universal characteristic.

Nonetheless, Figure 14 provides an interesting comparison of cosine
similarities derived from the training of a wide $4$-layer Perceptron (MLP)
with ReLU activations and a double-width ResNet-18. Despite a similar
parameter count, these two architectures exhibit a considerable performance
gap. Intriguingly, not only does the MLP not exhibit inferior geometrical
properties, but it actually shows greater regularity in cosine similarity
compared to the ResNet-18. This result suggests that the beneficial geometry
of neural loss landscapes is not simply a consequence of extensive
architectural tuning, but potentially a more intrinsic feature. Nonetheless,
prior work concluded that skip connections significantly simplify the loss
landscape at higher depth [27].

$\bullet$ High Dimensionality: Our conjecture is that the primary contributor
to the regular patterns observed by $\operatorname{RSI}$, $\operatorname{EB}$,
and $\gamma$ is the large dimensionality of neural loss landscapes. Assuming
that a significant number of dimensions maintain a degree of independence,
even when the gradient occasionally points in the ’wrong direction’ in certain
dimensions, this can be offset by averaging over a sufficiently vast number of
dimensions. However, formalizing such an effect is challenging due to the
evident dependencies between dimensions.

$\bullet$ Properties of Real-World Data: Lastly, the geometric simplicity of
optimization paths might be influenced by inherent properties of real-world
data distributions. For instance, it is commonly postulated that unstructured
data from real-world applications resides within lower-dimensional manifolds.
Analogous properties could be pivotal in shaping loss landscapes, which appear
more benign than what worst-case scenarios might suggest.

Figure 14: Comparison of cosine similarities derived from a CIFAR-10
classification task employing two distinct architectures: a straightforward
Multi-Layer Perceptron (MLP) and a more complex ResNet-18 structure.