Ecological resilience

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Ecological_resilience

Lake and Mulga ecosystems with alternative stable states

In ecology, resilience is the capacity of an ecosystem to respond to a perturbation or disturbance by resisting damage and subsequently recovering. Such perturbations and disturbances can include stochastic events such as fires, flooding, windstorms, insect population explosions, and human activities such as deforestation, fracking of the ground for oil extraction, pesticide sprayed in soil, and the introduction of exotic plant or animal species. Disturbances of sufficient magnitude or duration can profoundly affect an ecosystem and may force an ecosystem to reach a threshold beyond which a different regime of processes and structures predominates. When such thresholds are associated with a critical or bifurcation point, these regime shifts may also be referred to as critical transitions.

Human activities that adversely affect ecological resilience such as reduction of biodiversity, exploitation of natural resources, pollution, land use, and anthropogenic climate change are increasingly causing regime shifts in ecosystems, often to less desirable and degraded conditions. Interdisciplinary discourse on resilience now includes consideration of the interactions of humans and ecosystems via socio-ecological systems, and the need for shift from the maximum sustainable yield paradigm to environmental resource management and ecosystem management, which aim to build ecological resilience through "resilience analysis, adaptive resource management, and adaptive governance".Ecological resilience has inspired other fields and continues to challenge the way they interpret resilience, e.g. supply chain resilience.

Definitions

The IPCC Sixth Assessment Report defines resilience as, “not just the ability to maintain essential function, identity and structure, but also the capacity for transformation.” The IPCC considers resilience both in terms of ecosystem recovery as well as the recovery and adaptation of human societies to natural disasters.

The concept of resilience in ecological systems was first introduced by the Canadian ecologist C.S. Holling in order to describe the persistence of natural systems in the face of changes in ecosystem variables due to natural or anthropogenic causes. Resilience has been defined in two ways in ecological literature:

1. as the time required for an ecosystem to return to an equilibrium or steady-state following a perturbation (which is also defined as stability by some authors). This definition of resilience is used in other fields such as physics and engineering, and hence has been termed ‘engineering resilience’ by Holling.
2. as "the capacity of a system to absorb disturbance and reorganize while undergoing change so as to still retain essentially the same function, structure, identity, and feedbacks".

The second definition has been termed ‘ecological resilience’, and it presumes the existence of multiple stable states or regimes.

For example, some shallow temperate lakes can exist within either clear water regime, which provides many ecosystem services, or a turbid water regime, which provides reduced ecosystem services and can produce toxic algae blooms. The regime or state is dependent upon lake phosphorus cycles, and either regime can be resilient dependent upon the lake's ecology and management.

Likewise, Mulga woodlands of Australia can exist in a grass-rich regime that supports sheep herding, or a shrub-dominated regime of no value for sheep grazing. Regime shifts are driven by the interaction of fire, herbivory, and variable rainfall. Either state can be resilient dependent upon management.

Theory

Three levels of a panarchy, three adaptive cycles, and two cross-level linkages (remember and revolt)

Ecologists Brian Walker, C S Holling and others describe four critical aspects of resilience: latitude, resistance, precariousness, and panarchy.

The first three can apply both to a whole system or the sub-systems that make it up.

1. Latitude: the maximum amount a system can be changed before losing its ability to recover (before crossing a threshold which, if breached, makes recovery difficult or impossible).
2. Resistance: the ease or difficulty of changing the system; how “resistant” it is to being changed.
3. Precariousness: how close the current state of the system is to a limit or “threshold.”.
4. Panarchy: the degree to which a certain hierarchical level of an ecosystem is influenced by other levels. For example, organisms living in communities that are in isolation from one another may be organized differently from the same type of organism living in a large continuous population, thus the community-level structure is influenced by population-level interactions.

Closely linked to resilience is adaptive capacity, which is the property of an ecosystem that describes change in stability landscapes and resilience. Adaptive capacity in socio-ecological systems refers to the ability of humans to deal with change in their environment by observation, learning and altering their interactions.

Human impacts

Resilience refers to ecosystem's stability and capability of tolerating disturbance and restoring itself.  If the disturbance is of sufficient magnitude or duration, a threshold may be reached where the ecosystem undergoes a regime shift, possibly permanently. Sustainable use of environmental goods and services requires understanding and consideration of the resilience of the ecosystem and its limits. However, the elements which influence ecosystem resilience are complicated. For example, various elements such as the water cycle, fertility, biodiversity, plant diversity and climate, interact fiercely and affect different systems.

There are many areas where human activity impacts upon and is also dependent upon the resilience of terrestrial, aquatic and marine ecosystems. These include agriculture, deforestation, pollution, mining, recreation, overfishing, dumping of waste into the sea and climate change.

Agriculture

See also: agricultural expansion

Agriculture can be used as a significant case study in which the resilience of terrestrial ecosystems should be considered. The organic matter (elements carbon and nitrogen) in soil, which is supposed to be recharged by multiple plants, is the main source of nutrients for crop growth. In response to global food demand and shortages, however, intensive agriculture practices including the application of herbicides to control weeds, fertilisers to accelerate and increase crop growth and pesticides to control insects, reduce plant biodiversity while the supply of organic matter to replenish soil nutrients and prevent surface runoff is diminished. This leads to a reduction in soil fertility and productivity. More sustainable agricultural practices would take into account and estimate the resilience of the land and monitor and balance the input and output of organic matter.

Deforestation

The term deforestation has a meaning that covers crossing the threshold of forest's resilience and losing its ability to return to its originally stable state. To recover itself, a forest ecosystem needs suitable interactions among climate conditions and bio-actions, and enough area. In addition, generally, the resilience of a forest system allows recovery from a relatively small scale of damage (such as lightning or landslide) of up to 10 percent of its area. The larger the scale of damage, the more difficult it is for the forest ecosystem to restore and maintain its balance.

Deforestation also decreases biodiversity of both plant and animal life and can lead to an alteration of the climatic conditions of an entire area. According to the IPCC Sixth Assessment Report, carbon emissions due to land use and land use changes predominantly come from deforestation, thereby increasing the long-term exposure of forest ecosystems to drought and other climate change-induced damages. Deforestation can also lead to species extinction, which can have a domino effect particularly when keystone species are removed or when a significant number of species is removed and their ecological function is lost.

Climate change

Climate resilience is a concept to describe how well people or ecosystems are prepared to bounce back from certain climate hazard events. The formal definition of the term is the "capacity of social, economic and ecosystems to cope with a hazardous event or trend or disturbance". For example, climate resilience can be the ability to recover from climate-related shocks such as floods and droughts. Different actions can increase climate resilience of communities and ecosystems to help them cope. They can help to keep systems working in the face of external forces. For example, building a seawall to protect a coastal community from flooding might help maintain existing ways of life there.

Overfishing

It has been estimated by the United Nations Food and Agriculture Organisation that over 70% of the world's fish stocks are either fully exploited or depleted which means overfishing threatens marine ecosystem resilience and this is mostly by rapid growth of fishing technology. One of the negative effects on marine ecosystems is that over the last half-century the stocks of coastal fish have had a huge reduction as a result of overfishing for its economic benefits. Blue fin tuna is at particular risk of extinction. Depletion of fish stocks results in lowered biodiversity and consequently imbalance in the food chain, and increased vulnerability to disease.

In addition to overfishing, coastal communities are suffering the impacts of growing numbers of large commercial fishing vessels in causing reductions of small local fishing fleets. Many local lowland rivers which are sources of fresh water have become degraded because of the inflows of pollutants and sediments.

Dumping of waste into the sea

Dumping both depends upon ecosystem resilience whilst threatening it. Dumping of sewage and other contaminants into the ocean is often undertaken for the dispersive nature of the oceans and adaptive nature and ability for marine life to process the marine debris and contaminants. However, waste dumping threatens marine ecosystems by poisoning marine life and eutrophication.

Poisoning marine life

According to the International Maritime Organisation oil spills can have serious effects on marine life. The OILPOL Convention recognized that most oil pollution resulted from routine shipboard operations such as the cleaning of cargo tanks.  In the 1950s, the normal practice was simply to wash the tanks out with water and then pump the resulting mixture of oil and water into the sea. OILPOL 54   prohibited the dumping of oily wastes within a certain distance from land and in 'special areas' where the danger to the environment was especially acute. In 1962 the limits were extended by means of an amendment adopted at a conference organized by IMO. Meanwhile, IMO in 1965 set up a Subcommittee on Oil Pollution, under the auspices of its Maritime Safety committee, to address oil pollution issues.

The threat of oil spills to marine life is recognised by those likely to be responsible for the pollution, such as the International Tanker Owners Pollution Federation:

The marine ecosystem is highly complex and natural fluctuations in species composition, abundance and distribution are a basic feature of its normal function. The extent of damage can therefore be difficult to detect against this background variability. Nevertheless, the key to understanding damage and its importance is whether spill effects result in a downturn in breeding success, productivity, diversity and the overall functioning of the system. Spills are not the only pressure on marine habitats; chronic urban and industrial contamination or the exploitation of the resources they provide are also serious threats.

Eutrophication and algal blooms

The Woods Hole Oceanographic Institution calls nutrient pollution the most widespread, chronic environmental problem in the coastal ocean. The discharges of nitrogen, phosphorus, and other nutrients come from agriculture, waste disposal, coastal development, and fossil fuel use. Once nutrient pollution reaches the coastal zone, it stimulates harmful overgrowths of algae, which can have direct toxic effects and ultimately result in low-oxygen conditions. Certain types of algae are toxic. Overgrowths of these algae result in harmful algal blooms, which are more colloquially referred to as "red tides" or "brown tides". Zooplankton eat the toxic algae and begin passing the toxins up the food chain, affecting edibles like clams, and ultimately working their way up to seabirds, marine mammals, and humans. The result can be illness and sometimes death.

Sustainable development

Further information: Sustainable development

There is increasing awareness that a greater understanding and emphasis of ecosystem resilience is required to reach the goal of sustainable development. A similar conclusion is drawn by Perman et al. who use resilience to describe one of 6 concepts of sustainability; "A sustainable state is one which satisfies minimum conditions for ecosystem resilience through time". Resilience science has been evolving over the past decade, expanding beyond ecology to reflect systems of thinking in fields such as economics and political science. And, as more and more people move into densely populated cities, using massive amounts of water, energy, and other resources, the need to combine these disciplines to consider the resilience of urban ecosystems and cities is of paramount importance.

Academic perspectives

The interdependence of ecological and social systems has gained renewed recognition since the late 1990s by academics including Berkes and Folke and developed further in 2002 by Folke et al. As the concept of sustainable development has evolved beyond the 3 pillars of sustainable development to place greater political emphasis on economic development. This is a movement which causes wide concern in environmental and social forums and which Clive Hamilton describes as "the growth fetish".

The purpose of ecological resilience that is proposed is ultimately about averting our extinction as Walker cites Holling in his paper: "[..] "resilience is concerned with [measuring] the probabilities of extinction” (1973, p. 20)". Becoming more apparent in academic writing is the significance of the environment and resilience in sustainable development. Folke et al state that the likelihood of sustaining development is raised by "Managing for resilience" whilst Perman et al. propose that safeguarding the environment to "deliver a set of services" should be a "necessary condition for an economy to be sustainable". The growing application of resilience to sustainable development has produced a diversity of approaches and scholarly debates.

The flaw of the free market

The challenge of applying the concept of ecological resilience to the context of sustainable development is that it sits at odds with conventional economic ideology and policy making. Resilience questions the free market model within which global markets operate. Inherent to the successful operation of a free market is specialisation which is required to achieve efficiency and increase productivity. This very act of specialisation weakens resilience by permitting systems to become accustomed to and dependent upon their prevailing conditions. In the event of unanticipated shocks; this dependency reduces the ability of the system to adapt to these changes. Correspondingly; Perman et al. note that; "Some economic activities appear to reduce resilience, so that the level of disturbance to which the ecosystem can be subjected to without parametric change taking place is reduced".

Moving beyond sustainable development

Berkes and Folke table a set of principles to assist with "building resilience and sustainability" which consolidate approaches of adaptive management, local knowledge-based management practices and conditions for institutional learning and self-organisation.

More recently, it has been suggested by Andrea Ross that the concept of sustainable development is no longer adequate in assisting policy development fit for today's global challenges and objectives. This is because the concept of sustainable development is "based on weak sustainability" which doesn't take account of the reality of "limits to earth's resilience". Ross draws on the impact of climate change on the global agenda as a fundamental factor in the "shift towards ecological sustainability" as an alternative approach to that of sustainable development.

Because climate change is a major and growing driver of biodiversity loss, and that biodiversity and ecosystem functions and services, significantly contribute to climate change adaptation, mitigation and disaster risk reduction, proponents of ecosystem-based adaptation suggest that the resilience of vulnerable human populations and the ecosystem services upon which they depend are critical factors for sustainable development in a changing climate.

In environmental policy

Scientific research associated with resilience is beginning to play a role in influencing policy-making and subsequent environmental decision making.

This occurs in a number of ways:

• Observed resilience within specific ecosystems drives management practice. When resilience is observed to be low, or impact seems to be reaching the threshold, management response can be to alter human behavior to result in less adverse impact to the ecosystem.
• Ecosystem resilience impacts upon the way that development is permitted/environmental decision making is undertaken, similar to the way that existing ecosystem health impacts upon what development is permitted. For instance, remnant vegetation in the states of Queensland and New South Wales are classified in terms of ecosystem health and abundance. Any impact that development has upon threatened ecosystems must consider the health and resilience of these ecosystems. This is governed by the Threatened Species Conservation Act 1995 in New South Wales  and the Vegetation Management Act 1999 in Queensland.
• International level initiatives aim at improving socio-ecological resilience worldwide through the cooperation and contributions of scientific and other experts. An example of such an initiative is the Millennium Ecosystem Assessment whose objective is "to assess the consequences of ecosystem change for human well-being and the scientific basis for action needed to enhance the conservation and sustainable use of those systems and their contribution to human well-being". Similarly, the United Nations Environment Programme aim is "to provide leadership and encourage partnership in caring for the environment by inspiring, informing, and enabling nations and peoples to improve their quality of life without compromising that of future generations.

Environmental management in legislation

Ecological resilience and the thresholds by which resilience is defined are closely interrelated in the way that they influence environmental policy-making, legislation and subsequently environmental management. The ability of ecosystems to recover from certain levels of environmental impact is not explicitly noted in legislation, however, because of ecosystem resilience, some levels of environmental impact associated with development are made permissible by environmental policy-making and ensuing legislation.

Some examples of the consideration of ecosystem resilience within legislation include:

• Environmental Planning and Assessment Act 1979 (NSW)  – A key goal of the Environmental Assessment procedure is to determine whether proposed development will have a significant impact upon ecosystems.
• Protection of the Environment (Operations) Act 1997 (NSW)  – Pollution control is dependent upon keeping levels of pollutants emitted by industrial and other human activities below levels which would be harmful to the environment and its ecosystems. Environmental protection licenses are administered to maintain the environmental objectives of the POEO Act and breaches of license conditions can attract heavy penalties and in some cases criminal convictions.
• Threatened Species Conservation Act 1995 (NSW)  – This Act seeks to protect threatened species while balancing it with development.

History

The theoretical basis for many of the ideas central to climate resilience have actually existed since the 1960s. Originally an idea defined for strictly ecological systems, resilience in ecology was initially outlined by C.S. Holling as the capacity for ecological systems and relationships within those systems to persist and absorb changes to "state variables, driving variables, and parameters." This definition helped form the foundation for the notion of ecological equilibrium: the idea that the behavior of natural ecosystems is dictated by a homeostatic drive towards some stable set point. Under this school of thought (which maintained quite a dominant status during this time period), ecosystems were perceived to respond to disturbances largely through negative feedback systems – if there is a change, the ecosystem would act to mitigate that change as much as possible and attempt to return to its prior state.

As greater amounts of scientific research in ecological adaptation and natural resource management was conducted, it became clear that oftentimes, natural systems were subjected to dynamic, transient behaviors that changed how they reacted to significant changes in state variables: rather than work back towards a predetermined equilibrium, the absorbed change was harnessed to establish a new baseline to operate under. Rather than minimize imposed changes, ecosystems could integrate and manage those changes, and use them to fuel the evolution of novel characteristics. This new perspective of resilience as a concept that inherently works synergistically with elements of uncertainty and entropy first began to facilitate changes in the field of adaptive management and environmental resources, through work whose basis was built by Holling and colleagues yet again.

By the mid 1970s, resilience began gaining momentum as an idea in anthropology, culture theory, and other social sciences. There was significant work in these relatively non-traditional fields that helped facilitate the evolution of the resilience perspective as a whole. Part of the reason resilience began moving away from an equilibrium-centric view and towards a more flexible, malleable description of social-ecological systems was due to work such as that of Andrew Vayda and Bonnie McCay in the field of social anthropology, where more modern versions of resilience were deployed to challenge traditional ideals of cultural dynamics.

Gradient descent

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Gradient_descent

Gradient descent is a method for unconstrained mathematical optimization. It is a first-order iterative algorithm for minimizing a differentiable multivariate function.

The idea is to take repeated steps in the opposite direction of the gradient (or approximate gradient) of the function at the current point, because this is the direction of steepest descent. Conversely, stepping in the direction of the gradient will lead to a trajectory that maximizes that function; the procedure is then known as gradient ascent. It is particularly useful in machine learning and artificial intelligence for minimizing the cost or loss function. Gradient descent should not be confused with local search algorithms, although both are iterative methods for optimization.

Gradient descent is generally attributed to Augustin-Louis Cauchy, who first suggested it in 1847. Jacques Hadamard independently proposed a similar method in 1907. Its convergence properties for non-linear optimization problems were first studied by Haskell Curry in 1944, with the method becoming increasingly well-studied and used in the following decades.

A simple extension of gradient descent, stochastic gradient descent, serves as the most basic algorithm used for training most deep networks today.

Description

Illustration of gradient descent on a series of level sets

Gradient descent is based on the observation that if the multi-variable function ${\displaystyle f(\mathbf{x})}$ is defined and differentiable in a neighborhood of a point ${\displaystyle \mathbf{a}}$, then ${\displaystyle f(\mathbf{x})}$ decreases fastest if one goes from ${\displaystyle \mathbf{a}}$ in the direction of the negative gradient of ${\displaystyle f}$ at ${\displaystyle \mathbf{a},-\mathrm{\nabla }f(\mathbf{a})}$. It follows that, if

${\displaystyle {\mathbf{a}}_{n+1}={\mathbf{a}}_n-\eta \mathrm{\nabla }f({\mathbf{a}}_n)}$

for a small enough step size or learning rate ${\displaystyle \eta \in {\mathbb{R}}_{+}}$, then ${\displaystyle f({\mathbf{a}}_{\mathbf{n}})\ge f({\mathbf{a}}_{\mathbf{n}\mathbf{+}\mathbf{1}})}$. In other words, the term ${\displaystyle \eta \mathrm{\nabla }f(\mathbf{a})}$ is subtracted from ${\displaystyle \mathbf{a}}$ because we want to move against the gradient, toward the local minimum. With this observation in mind, one starts with a guess ${\displaystyle {\mathbf{x}}_0}$ for a local minimum of ${\displaystyle f}$, and considers the sequence ${\displaystyle {\mathbf{x}}_0,{\mathbf{x}}_1,{\mathbf{x}}_2,\dots }$ such that

${\displaystyle {\mathbf{x}}_{n+1}={\mathbf{x}}_n-{\eta }_n\mathrm{\nabla }f({\mathbf{x}}_n),n\ge 0.}$

We have a monotonic sequence

${\displaystyle f({\mathbf{x}}_0)\ge f({\mathbf{x}}_1)\ge f({\mathbf{x}}_2)\ge \cdots ,}$

so the sequence ${\displaystyle ({\mathbf{x}}_n)}$ converges to the desired local minimum. Note that the value of the step size ${\displaystyle \eta }$ is allowed to change at every iteration.

It is possible to guarantee the convergence to a local minimum under certain assumptions on the function ${\displaystyle f}$ (for example, ${\displaystyle f}$ convex and ${\displaystyle \mathrm{\nabla }f}$ Lipschitz) and particular choices of ${\displaystyle \eta }$. Those include the sequence

${\displaystyle {\eta }_n=\frac{\left|{\left({\mathbf{x}}_n-{\mathbf{x}}_{n-1}\right)}^{\mathrm{\top }}\left[\mathrm{\nabla }f({\mathbf{x}}_n)-\mathrm{\nabla }f({\mathbf{x}}_{n-1})\right]\right|}{{\Vert \mathrm{\nabla }f({\mathbf{x}}_n)-\mathrm{\nabla }f({\mathbf{x}}_{n-1})\Vert }^2}}$

as in the Barzilai-Borwein method, or a sequence ${\displaystyle {\eta }_n}$ satisfying the Wolfe conditions (which can be found by using line search). When the function ${\displaystyle f}$ is convex, all local minima are also global minima, so in this case gradient descent can converge to the global solution.

This process is illustrated in the adjacent picture. Here, ${\displaystyle f}$ is assumed to be defined on the plane, and that its graph has a bowl shape. The blue curves are the contour lines, that is, the regions on which the value of ${\displaystyle f}$ is constant. A red arrow originating at a point shows the direction of the negative gradient at that point. Note that the (negative) gradient at a point is orthogonal to the contour line going through that point. We see that gradient descent leads us to the bottom of the bowl, that is, to the point where the value of the function ${\displaystyle f}$ is minimal.

An analogy for understanding gradient descent

Fog in the mountains

The basic intuition behind gradient descent can be illustrated by a hypothetical scenario. People are stuck in the mountains and are trying to get down (i.e., trying to find the global minimum). There is heavy fog such that visibility is extremely low. Therefore, the path down the mountain is not visible, so they must use local information to find the minimum. They can use the method of gradient descent, which involves looking at the steepness of the hill at their current position, then proceeding in the direction with the steepest descent (i.e., downhill). If they were trying to find the top of the mountain (i.e., the maximum), then they would proceed in the direction of steepest ascent (i.e., uphill). Using this method, they would eventually find their way down the mountain or possibly get stuck in some hole (i.e., local minimum or saddle point), like a mountain lake. However, assume also that the steepness of the hill is not immediately obvious with simple observation, but rather it requires a sophisticated instrument to measure, which the people happen to have at that moment. It takes quite some time to measure the steepness of the hill with the instrument. Thus, they should minimize their use of the instrument if they want to get down the mountain before sunset. The difficulty then is choosing the frequency at which they should measure the steepness of the hill so as not to go off track.

In this analogy, the people represent the algorithm, and the path taken down the mountain represents the sequence of parameter settings that the algorithm will explore. The steepness of the hill represents the slope of the function at that point. The instrument used to measure steepness is differentiation. The direction they choose to travel in aligns with the gradient of the function at that point. The amount of time they travel before taking another measurement is the step size.

Choosing the step size and descent direction

Since using a step size ${\displaystyle \eta }$ that is too small would slow convergence, and a ${\displaystyle \eta }$ too large would lead to overshoot and divergence, finding a good setting of ${\displaystyle \eta }$ is an important practical problem. Philip Wolfe also advocated using "clever choices of the [descent] direction" in practice. While using a direction that deviates from the steepest descent direction may seem counter-intuitive, the idea is that the smaller slope may be compensated for by being sustained over a much longer distance.

To reason about this mathematically, consider a direction ${\displaystyle {\mathbf{p}}_n}$ and step size ${\displaystyle {\eta }_n}$ and consider the more general update:

${\displaystyle {\mathbf{a}}_{n+1}={\mathbf{a}}_n-{\eta }_n{\mathbf{p}}_n}$.

Finding good settings of ${\displaystyle {\mathbf{p}}_n}$ and ${\displaystyle {\eta }_n}$ requires some thought. First of all, we would like the update direction to point downhill. Mathematically, letting ${\displaystyle {\theta }_n}$ denote the angle between ${\displaystyle -\mathrm{\nabla }f({\mathbf{a}}_{\mathbf{n}})}$ and ${\displaystyle {\mathbf{p}}_n}$, this requires that ${\displaystyle \cos {\theta }_n>0.}$ To say more, we need more information about the objective function that we are optimising. Under the fairly weak assumption that ${\displaystyle f}$ is continuously differentiable, we may prove that:

${\displaystyle f({\mathbf{a}}_{n+1})\le f({\mathbf{a}}_n)-{\eta }_n\Vert \mathrm{\nabla }f({\mathbf{a}}_n){\Vert }_2\Vert {\mathbf{p}}_n{\Vert }_2\left(\cos {\theta }_n-\underset{t\in [0,1]}{max}\frac{\Vert \mathrm{\nabla }f({\mathbf{a}}_n-t{\eta }_n{\mathbf{p}}_n)-\mathrm{\nabla }f({\mathbf{a}}_n){\Vert }_2}{\Vert \mathrm{\nabla }f({\mathbf{a}}_n){\Vert }_2}\right)}$

1

This inequality implies that the amount by which we can be sure the function ${\displaystyle f}$ is decreased depends on a trade off between the two terms in square brackets. The first term in square brackets measures the angle between the descent direction and the negative gradient. The second term measures how quickly the gradient changes along the descent direction.

In principle inequality (1) could be optimized over ${\displaystyle {\mathbf{p}}_n}$ and ${\displaystyle {\eta }_n}$ to choose an optimal step size and direction. The problem is that evaluating the second term in square brackets requires evaluating ${\displaystyle \mathrm{\nabla }f({\mathbf{a}}_n-t{\eta }_n{\mathbf{p}}_n)}$, and extra gradient evaluations are generally expensive and undesirable. Some ways around this problem are:

• Forgo the benefits of a clever descent direction by setting ${\displaystyle {\mathbf{p}}_n=\mathrm{\nabla }f({\mathbf{a}}_{\mathbf{n}})}$, and use line search to find a suitable step-size ${\displaystyle {\gamma }_n}$, such as one that satisfies the Wolfe conditions. A more economic way of choosing learning rates is backtracking line search, a method that has both good theoretical guarantees and experimental results. Note that one does not need to choose ${\displaystyle {\mathbf{p}}_n}$ to be the gradient; any direction that has positive inner product with the gradient will result in a reduction of the function value (for a sufficiently small value of ${\displaystyle {\eta }_n}$).
• Assuming that ${\displaystyle f}$ is twice-differentiable, use its Hessian ${\displaystyle {\mathrm{\nabla }}^{2}f}$ to estimate ${\displaystyle \Vert \mathrm{\nabla }f({\mathbf{a}}_n-t{\eta }_n{\mathbf{p}}_n)-\mathrm{\nabla }f({\mathbf{a}}_n){\Vert }_2\approx \Vert t{\eta }_n{\mathrm{\nabla }}^{2}f({\mathbf{a}}_n){\mathbf{p}}_n\Vert .}$Then choose ${\displaystyle {\mathbf{p}}_n}$ and ${\displaystyle {\eta }_n}$ by optimising inequality (1).
• Assuming that ${\displaystyle \mathrm{\nabla }f}$ is Lipschitz, use its Lipschitz constant ${\displaystyle L}$ to bound ${\displaystyle \Vert \mathrm{\nabla }f({\mathbf{a}}_n-t{\eta }_n{\mathbf{p}}_n)-\mathrm{\nabla }f({\mathbf{a}}_n){\Vert }_2\le Lt{\eta }_n\Vert {\mathbf{p}}_n\Vert .}$ Then choose ${\displaystyle {\mathbf{p}}_n}$ and ${\displaystyle {\eta }_n}$ by optimising inequality (1).
• Build a custom model of ${\displaystyle \underset{t\in [0,1]}{max}\frac{\Vert \mathrm{\nabla }f({\mathbf{a}}_n-t{\eta }_n{\mathbf{p}}_n)-\mathrm{\nabla }f({\mathbf{a}}_n){\Vert }_2}{\Vert \mathrm{\nabla }f({\mathbf{a}}_n){\Vert }_2}}$ for ${\displaystyle f}$. Then choose ${\displaystyle {\mathbf{p}}_n}$ and ${\displaystyle {\eta }_n}$ by optimising inequality (1).
• Under stronger assumptions on the function ${\displaystyle f}$ such as convexity, more advanced techniques may be possible.

Usually by following one of the recipes above, convergence to a local minimum can be guaranteed. When the function ${\displaystyle f}$ is convex, all local minima are also global minima, so in this case gradient descent can converge to the global solution.

Solution of a linear system

The steepest descent algorithm applied to the Wiener filter

Gradient descent can be used to solve a system of linear equations

${\displaystyle \mathbf{A}\mathbf{x}-\mathbf{b}=0}$

reformulated as a quadratic minimization problem. If the system matrix ${\displaystyle \mathbf{A}}$ is real symmetric and positive-definite, an objective function is defined as the quadratic function, with minimization of

${\displaystyle f(\mathbf{x})={\mathbf{x}}^{\mathrm{\top }}\mathbf{A}\mathbf{x}-2{\mathbf{x}}^{\mathrm{\top }}\mathbf{b},}$

so that

${\displaystyle \mathrm{\nabla }f(\mathbf{x})=2(\mathbf{A}\mathbf{x}-\mathbf{b}).}$

For a general real matrix ${\displaystyle \mathbf{A}}$, linear least squares define

${\displaystyle f(\mathbf{x})={\Vert \mathbf{A}\mathbf{x}-\mathbf{b}\Vert }^2.}$

In traditional linear least squares for real ${\displaystyle \mathbf{A}}$ and ${\displaystyle \mathbf{b}}$ the Euclidean norm is used, in which case

${\displaystyle \mathrm{\nabla }f(\mathbf{x})=2{\mathbf{A}}^{\mathrm{\top }}(\mathbf{A}\mathbf{x}-\mathbf{b}).}$

The line search minimization, finding the locally optimal step size ${\displaystyle \eta }$ on every iteration, can be performed analytically for quadratic functions, and explicit formulas for the locally optimal ${\displaystyle \eta }$ are known.

For example, for real symmetric and positive-definite matrix ${\displaystyle \mathbf{A}}$, a simple algorithm can be as follows,

${\displaystyle \begin{array}{rl}& \text{repeat in the loop:}\\ & \mathbf{r}:=\mathbf{b}-\mathbf{A}\mathbf{x}\\ & \eta :={\mathbf{r}}^{\mathrm{\top }}\mathbf{r}/{\mathbf{r}}^{\mathrm{\top }}\mathbf{A}\mathbf{r}\\ & \mathbf{x}:=\mathbf{x}+\eta \mathbf{r}\\ & \text{if }{\mathbf{r}}^{\mathrm{\top }}\mathbf{r}\text{ is sufficiently small, then exit loop}\\ & \text{end repeat loop}\\ & \text{return }\mathbf{x}\text{ as the result}\end{array}}$

To avoid multiplying by ${\displaystyle \mathbf{A}}$ twice per iteration, we note that ${\displaystyle \mathbf{x}:=\mathbf{x}+\eta \mathbf{r}}$ implies ${\displaystyle \mathbf{r}:=\mathbf{r}-\eta \mathbf{A}\mathbf{r}}$, which gives the traditional algorithm,

${\displaystyle \begin{array}{rl}& \mathbf{r}:=\mathbf{b}-\mathbf{A}\mathbf{x}\\ & \text{repeat in the loop:}\\ & \eta :={\mathbf{r}}^{\mathrm{\top }}\mathbf{r}/{\mathbf{r}}^{\mathrm{\top }}\mathbf{A}\mathbf{r}\\ & \mathbf{x}:=\mathbf{x}+\eta \mathbf{r}\\ & \text{if }{\mathbf{r}}^{\mathrm{\top }}\mathbf{r}\text{ is sufficiently small, then exit loop}\\ & \mathbf{r}:=\mathbf{r}-\eta \mathbf{A}\mathbf{r}\\ & \text{end repeat loop}\\ & \text{return }\mathbf{x}\text{ as the result}\end{array}}$

Convergence path of steepest descent method for A = [[2, 2], [2, 3]]

The method is rarely used for solving linear equations, with the conjugate gradient method being one of the most popular alternatives. The number of gradient descent iterations is commonly proportional to the spectral condition number ${\displaystyle \kappa (\mathbf{A})}$ of the system matrix ${\displaystyle \mathbf{A}}$ (the ratio of the maximum to minimum eigenvalues of ${\displaystyle {\mathbf{A}}^{\mathrm{\top }}\mathbf{A}}$), while the convergence of conjugate gradient method is typically determined by a square root of the condition number, i.e., is much faster. Both methods can benefit from preconditioning, where gradient descent may require less assumptions on the preconditioner.

Geometric behavior and residual orthogonality

In steepest descent applied to solving ${\displaystyle \mathbf{A}\mathbf{x}=\mathbf{b}}$, where ${\displaystyle \mathbf{A}}$ is symmetric positive-definite, the residual vectors ${\displaystyle {\mathbf{r}}_k=\mathbf{b}-\mathbf{A}{\mathbf{x}}_k}$ are orthogonal across iterations:

${\displaystyle ⟨{\mathbf{r}}_{k+1},{\mathbf{r}}_k⟩=0.}$

Because each step is taken in the steepest direction, steepest-descent steps alternate between directions aligned with the extreme axes of the elongated level sets. When ${\displaystyle \kappa (\mathbf{A})}$ is large, this produces a characteristic zig–zag path. The poor conditioning of ${\displaystyle \mathbf{A}}$ is the primary cause of the slow convergence, and orthogonality of successive residuals reinforces this alternation.

As shown in the image on the right, steepest descent converges slowly due to the high condition number of ${\displaystyle \mathbf{A}}$, and the orthogonality of residuals forces each new direction to undo the overshoot from the previous step. The result is a path that zigzags toward the solution. This inefficiency is one reason conjugate gradient or preconditioning methods are preferred.

Solution of a non-linear system

Gradient descent can also be used to solve a system of nonlinear equations. Below is an example that shows how to use the gradient descent to solve for three unknown variables, x₁, x₂, and x₃. This example shows one iteration of the gradient descent.

Consider the nonlinear system of equations

An animation showing the first 83 iterations of gradient descent applied to this example. Surfaces are isosurfaces of ${\displaystyle f({\mathbf{x}}^{(n)})}$ at current guess ${\displaystyle {\mathbf{x}}^{(n)}}$, and arrows show the direction of descent. Due to a small and constant step size, the convergence is slow.

${\displaystyle \{\begin{array}{l}3x_1-\cos (x_2{x}_3)-\frac{3}{2}=0\\ 4x_1^2-625x_2^2+2x_2-1=0\\ \exp (-x_1{x}_2)+20x_3+\frac{10\pi -3}{3}=0\end{array}}$

Let us introduce the associated function

${\displaystyle G(\mathbf{x})=\left[\begin{array}{c}3x_1-\cos (x_2{x}_3)-\frac{3}{2}\\ 4x_1^2-625x_2^2+2x_2-1\\ \exp (-x_1{x}_2)+20x_3+\frac{10\pi -3}{3}\end{array}\right],}$

where

${\displaystyle \mathbf{x}=\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right].}$

One might now define the objective function

${\displaystyle \begin{array}{rl}f(\mathbf{x})& =\frac{1}{2}{G}^{\mathrm{\top }}(\mathbf{x})G(\mathbf{x})\\ & =\frac{1}{2}[{\left(3x_1-\cos (x_2{x}_3)-\frac{3}{2}\right)}^2+{\left(4x_1^2-625x_2^2+2x_2-1\right)}^2+\\ & {\left(\exp (-x_1{x}_2)+20x_3+\frac{10\pi -3}{3}\right)}^2],\end{array}}$

which we will attempt to minimize. As an initial guess, let us use

${\displaystyle {\mathbf{x}}^{(0)}=\mathbf{0}=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right].}$

We know that

${\displaystyle {\mathbf{x}}^{(1)}=\mathbf{0}-{\eta }_0\mathrm{\nabla }f(\mathbf{0})=\mathbf{0}-{\eta }_0{J}_G(\mathbf{0}{)}^{\mathrm{\top }}G(\mathbf{0}),}$

where the Jacobian matrix ${\displaystyle J_G}$ is given by

${\displaystyle J_G(\mathbf{x})=\left[\begin{array}{ccc}3& \sin (x_2{x}_3)x_3& \sin (x_2{x}_3)x_2\\ 8x_1& -1250x_2+2& 0\\ -x_2\exp (-x_1{x}_2)& -x_1\exp (-x_1{x}_2)& 20\end{array}\right].}$

We calculate:

${\displaystyle J_G(\mathbf{0})=\left[\begin{array}{ccc}3& 0& 0\\ 0& 2& 0\\ 0& 0& 20\end{array}\right],G(\mathbf{0})=\left[\begin{array}{c}-2.5\\ -1\\ 10.472\end{array}\right].}$

Thus

${\displaystyle {\mathbf{x}}^{(1)}=\mathbf{0}-{\eta }_0\left[\begin{array}{c}-7.5\\ -2\\ 209.44\end{array}\right],}$

and

${\displaystyle f(\mathbf{0})=0.5\left((-2.5{)}^2+(-1{)}^2+(10.472{)}^2\right)=\mathrm{58.456.}}$

Now, a suitable ${\displaystyle {\eta }_0}$ must be found such that

${\displaystyle f\left({\mathbf{x}}^{(1)}\right)\le f\left({\mathbf{x}}^{(0)}\right)=f(\mathbf{0}).}$

This can be done with any of a variety of line search algorithms. One might also simply guess ${\displaystyle {\eta }_0=0.001,}$ which gives

${\displaystyle {\mathbf{x}}^{(1)}=\left[\begin{array}{c}0.0075\\ 0.002\\ -0.20944\end{array}\right].}$

Evaluating the objective function at this value, yields

${\displaystyle f\left({\mathbf{x}}^{(1)}\right)=0.5\left((-2.48{)}^2+(-1.00{)}^2+(6.28{)}^2\right)=\mathrm{23.306.}}$

The decrease from ${\displaystyle f(\mathbf{0})=58.456}$ to the next step's value of

${\displaystyle f\left({\mathbf{x}}^{(1)}\right)=23.306}$

is a sizable decrease in the objective function. Further steps would reduce its value further until an approximate solution to the system was found.

Gradient descent works in spaces of any number of dimensions, even in infinite-dimensional ones. In the latter case, the search space is typically a function space, and one calculates the Fréchet derivative of the functional to be minimized to determine the descent direction.

That gradient descent works in any number of dimensions (finite number at least) can be seen as a consequence of the Cauchy–Schwarz inequality, i.e. the magnitude of the inner (dot) product of two vectors of any dimension is maximized when they are colinear. In the case of gradient descent, that would be when the vector of independent variable adjustments is proportional to the gradient vector of partial derivatives.

The gradient descent can take many iterations to compute a local minimum with a required accuracy, if the curvature in different directions is very different for the given function. For such functions, preconditioning, which changes the geometry of the space to shape the function level sets like concentric circles, cures the slow convergence. Constructing and applying preconditioning can be computationally expensive, however.

The gradient descent can be modified via momentums (Nesterov, Polyak, and Frank–Wolfe) and heavy-ball parameters (exponential moving averages and positive-negative momentum). The main examples of such optimizers are Adam, DiffGrad, Yogi, AdaBelief, etc.

Methods based on Newton's method and inversion of the Hessian using conjugate gradient techniques can be better alternatives. Generally, such methods converge in fewer iterations, but the cost of each iteration is higher. An example is the BFGS method which consists in calculating on every step a matrix by which the gradient vector is multiplied to go into a "better" direction, combined with a more sophisticated line search algorithm, to find the "best" value of ${\displaystyle \eta .}$ For extremely large problems, where the computer-memory issues dominate, a limited-memory method such as L-BFGS should be used instead of BFGS or the steepest descent.

While it is sometimes possible to substitute gradient descent for a local search algorithm, gradient descent is not in the same family: although it is an iterative method for local optimization, it relies on an objective function's gradient rather than an explicit exploration of a solution space.

Gradient descent can be viewed as applying Euler's method for solving ordinary differential equations ${\displaystyle x^{\prime }(t)=-\mathrm{\nabla }f(x(t))}$ to a gradient flow. In turn, this equation may be derived as an optimal controller for the control system ${\displaystyle x^{\prime }(t)=u(t)}$ with ${\displaystyle u(t)}$ given in feedback form ${\displaystyle u(t)=-\mathrm{\nabla }f(x(t))}$.

Modifications

Gradient descent can converge to a local minimum and slow down in a neighborhood of a saddle point. Even for unconstrained quadratic minimization, gradient descent develops a zig–zag pattern of subsequent iterates as iterations progress, resulting in slow convergence. Multiple modifications of gradient descent have been proposed to address these deficiencies.

Fast gradient methods

Yurii Nesterov has proposed a simple modification that enables faster convergence for convex problems and has been since further generalized. For unconstrained smooth problems, the method is called the fast gradient method (FGM) or the accelerated gradient method (AGM). Specifically, if the differentiable function ${\displaystyle f}$ is convex and ${\displaystyle \mathrm{\nabla }f}$ is Lipschitz, and it is not assumed that ${\displaystyle f}$ is strongly convex, then the error in the objective value generated at each step ${\displaystyle k}$ by the gradient descent method will be bounded by $\mathcal{O}\left(k^{-1}\right)$. Using the Nesterov acceleration technique, the error decreases at $\mathcal{O}\left(k^{-2}\right)$. It is known that the rate ${\displaystyle \mathcal{O}\left(k^{-2}\right)}$ for the decrease of the cost function is optimal for first-order optimization methods. Nevertheless, there is the opportunity to improve the algorithm by reducing the constant factor. The optimized gradient method (OGM) reduces that constant by a factor of two and is an optimal first-order method for large-scale problems.

For constrained or non-smooth problems, Nesterov's FGM is called the fast proximal gradient method (FPGM), an acceleration of the proximal gradient method.

Momentum or heavy ball method

Trying to break the zig-zag pattern of gradient descent, the momentum or heavy ball method uses a momentum term in analogy to a heavy ball sliding on the surface of values of the function being minimized, or to mass movement in Newtonian dynamics through a viscous medium in a conservative force field. Gradient descent with momentum remembers the solution update at each iteration, and determines the next update as a linear combination of the gradient and the previous update. For unconstrained quadratic minimization, a theoretical convergence rate bound of the heavy ball method is asymptotically the same as that for the optimal conjugate gradient method.

This technique is used in stochastic gradient descent and as an extension to the backpropagation algorithms used to train artificial neural networks. In the direction of updating, stochastic gradient descent adds a stochastic property. The weights can be used to calculate the derivatives.

Extensions

Gradient descent can be extended to handle constraints by including a projection onto the set of constraints. This method is only feasible when the projection is efficiently computable on a computer. Under suitable assumptions, this method converges. This method is a specific case of the forward–backward algorithm for monotone inclusions (which includes convex programming and variational inequalities).

Gradient descent is a special case of mirror descent using the squared Euclidean distance as the given Bregman divergence.

Theoretical properties

The properties of gradient descent depend on the properties of the objective function and the variant of gradient descent used (for example, if a line search step is used). The assumptions made affect the convergence rate, and other properties, that can be proven for gradient descent. For example, if the objective is assumed to be strongly convex and lipschitz smooth, then gradient descent converges linearly with a fixed step size. Looser assumptions lead to either weaker convergence guarantees or require a more sophisticated step size selection.