Optimalisatieproblemen kunnen lastig zijn, maar ze zorgen ervoor dat de wereld beter werkt. Dit soort vragen, die streven naar de beste manier om iets te doen, zijn werkelijk overal. De gps van je telefoon berekent de kortste route naar je bestemming. Reiswebsites zoeken naar de goedkoopste combinatie van vluchten die past bij uw reisschema. En toepassingen voor machine learning, die leren door patronen in gegevens te analyseren, proberen de meest nauwkeurige en menselijke antwoorden op een gegeven vraag te geven.

Voor eenvoudige optimalisatieproblemen is het vinden van de beste oplossing slechts een kwestie van rekenen. Maar de real-world vragen die wiskundigen en wetenschappers interesseren, zijn zelden eenvoudig. In 1847 werkte de Franse wiskundige Augustin-Louis Cauchy aan een behoorlijk gecompliceerd voorbeeld - astronomische berekeningen - toen hij pionierde met een veelgebruikte optimalisatiemethode die nu bekend staat als gradiëntafdaling. De meeste machine learning-programma's zijn tegenwoordig sterk afhankelijk van de techniek, en andere velden gebruiken het ook om gegevens te analyseren en technische problemen op te lossen.

Wiskundigen hebben de gradiëntafdaling al meer dan 150 jaar geperfectioneerd, maar vorige maand Een studie bewezen dat een basisaanname over de techniek verkeerd kan zijn. "Er waren maar een paar keer dat ik verrast was, [alsof] mijn intuïtie gebroken was", zei Ben Grimmer, een toegepaste wiskundige aan de Johns Hopkins University en de enige auteur van de studie. Zijn contra-intuïtieve resultaten toonden aan dat gradiëntafdaling bijna drie keer sneller kan werken als het een lang geaccepteerde regel overtreedt voor het vinden van het beste antwoord op een bepaalde vraag. Hoewel de theoretische vooruitgang waarschijnlijk niet van toepassing is op de lastiger problemen die door machine learning worden aangepakt, heeft het ertoe geleid dat onderzoekers heroverwegen wat ze weten over de techniek.

"Het blijkt dat we niet volledig begrip hadden" van de theorie achter gradiëntafdaling, zei Shuvomoy Das Gupta, een optimalisatieonderzoeker aan het Massachusetts Institute of Technology. Nu, zei hij, zijn we "dichter bij het begrijpen van wat gradiëntafdaling doet."

De techniek zelf is bedrieglijk eenvoudig. Het maakt gebruik van een zogenaamde kostenfunctie, die eruitziet als een vloeiende, gebogen lijn die op en neer door een grafiek slingert. Voor elk punt op die lijn vertegenwoordigt de hoogte op de een of andere manier de kosten: hoeveel tijd, energie of fouten de bewerking zal opleveren wanneer deze is afgestemd op een specifieke instelling. Hoe hoger het punt, hoe verder het systeem verwijderd is van het ideaal. U wilt natuurlijk het laagste punt op deze lijn vinden, waar de kosten het kleinst zijn.

Gradiënt-afdalingsalgoritmen zoeken hun weg naar de bodem door een punt te kiezen en de helling (of helling) van de curve eromheen te berekenen, en vervolgens in de richting te gaan waar de helling het steilst is. Stel je voor dat je je in het donker een berg af voelt voelen. Je weet misschien niet precies waar je heen moet, hoe lang je moet wandelen of hoe dicht je uiteindelijk bij zeeniveau zult komen, maar als je de scherpste afdaling afdaalt, zou je uiteindelijk op het laagste punt in het gebied moeten aankomen.

In tegenstelling tot de metaforische bergbeklimmer, kunnen optimalisatieonderzoekers hun gradiënt-afdalingsalgoritmen programmeren om stappen van elke grootte te nemen. Reuzensprongen zijn verleidelijk maar ook riskant, omdat ze het antwoord voorbij kunnen schieten. In plaats daarvan is de conventionele wijsheid van het veld al decennia lang het nemen van babystapjes. In vergelijkingen met gradiëntafdaling betekent dit een stapgrootte niet groter dan 2, hoewel niemand kon bewijzen dat kleinere stapgroottes altijd beter waren.

Met de vooruitgang in computerondersteunde bewijstechnieken zijn optimalisatietheoretici begonnen met het testen van extremere technieken. Eerst in één studie geplaatst in 2022 en onlangs gepubliceerd in Wiskundig programmeren, gaven Das Gupta en anderen een computer de opdracht om de beste staplengtes te vinden voor een algoritme dat beperkt was tot het uitvoeren van slechts 50 stappen - een soort meta-optimalisatieprobleem, aangezien het probeerde de optimalisatie te optimaliseren. Ze ontdekten dat de meest optimale 50 stappen aanzienlijk in lengte varieerden, waarbij één stap in het midden van de reeks bijna lengte 37 bereikte, ver boven de typische limiet van lengte 2.

De bevindingen suggereerden dat optimalisatieonderzoekers iets hadden gemist. Geïntrigeerd probeerde Grimmer de numerieke resultaten van Das Gupta om te zetten in een meer algemene stelling. Om voorbij een willekeurige limiet van 50 stappen te komen, onderzocht Grimmer wat de optimale staplengte zou zijn voor een reeks die zich zou kunnen herhalen, waarbij hij bij elke herhaling dichter bij het optimale antwoord kwam. Hij liet de computer miljoenen permutaties van reeksen van staplengtes doorlopen, en hielp om de antwoorden te vinden die het snelst samenkwamen.

Grimmer ontdekte dat de snelste reeksen altijd één ding gemeen hadden: de middelste stap was altijd een grote. De grootte hing af van het aantal stappen in de zich herhalende reeks. Voor een reeks met drie stappen had de grote stap een lengte van 4.9. Voor een reeks van 15 stappen raadde het algoritme een stap aan met een lengte van 29.7. En voor een reeks van 127 stappen, de langste geteste, was de grote centrale sprong maar liefst 370. In eerste instantie klinkt dat als een absurd groot aantal, zei Grimmer, maar er waren in totaal genoeg stappen om die gigantische sprong goed te maken, dus zelfs als je voorbij de bodem waait, kun je nog steeds snel terug komen. Zijn paper toonde aan dat deze reeks bijna drie keer sneller op het optimale punt kan komen dan door constant kleine stapjes te nemen. "Soms moet je echt te veel inzetten", zei hij.

Deze cyclische benadering vertegenwoordigt een andere manier van denken over gradiëntafdaling, zei hij Aymeric Dieuleveut, een optimalisatieonderzoeker aan de École Polytechnique in Palaiseau, Frankrijk. "Deze intuïtie, dat ik niet stap voor stap moet denken, maar als een aantal opeenvolgende stappen - ik denk dat dit iets is dat veel mensen negeren", zei hij. "Het is niet de manier waarop het wordt geleerd." (Grimmer merkt op dat deze herkadering ook voorgestelde voor een vergelijkbare klasse problemen in een masterscriptie uit 2018 van Jason Altschuler, een optimalisatieonderzoeker die nu aan de Universiteit van Pennsylvania werkt.)

Hoewel deze inzichten de manier waarop onderzoekers denken over gradiëntafdaling kunnen veranderen, zullen ze waarschijnlijk niet veranderen hoe de techniek momenteel wordt gebruikt. Het artikel van Grimmer concentreerde zich alleen op vloeiende functies, die geen scherpe knikken hebben, en convexe functies, die de vorm hebben van een kom en slechts één optimale waarde aan de onderkant hebben. Dit soort functies zijn fundamenteel voor de theorie, maar minder relevant in de praktijk; de optimalisatieprogramma's die onderzoekers van machine learning gebruiken, zijn meestal veel ingewikkelder. Deze vereisen versies van gradiëntafdaling met "zoveel toeters en bellen en zoveel nuances", zei Grimmer.

Sommige van deze opgevoerde technieken kunnen sneller gaan dan de grote stappen van Grimmer, zei Gauthier Gidel, een onderzoeker op het gebied van optimalisatie en machine learning aan de Universiteit van Montreal. Maar deze technieken brengen extra operationele kosten met zich mee, dus de hoop was dat regelmatige gradiëntafdaling zou kunnen winnen met de juiste combinatie van stapgroottes. Helaas is de drievoudige versnelling van de nieuwe studie niet genoeg.

"Het laat een marginale verbetering zien", zei Gidel. "Maar ik denk dat de echte vraag is: kunnen we deze kloof echt dichten?"

De resultaten roepen ook een extra theoretisch mysterie op dat Grimmer 's nachts wakker heeft gehouden. Waarom hadden de ideale patronen van stapgroottes allemaal zo'n symmetrische vorm? Niet alleen is de grootste stap altijd pal in het midden, maar hetzelfde patroon verschijnt aan weerszijden ervan: blijf inzoomen en de reeks onderverdelen, zei hij, en je krijgt een "bijna fractaal patroon" van grotere stappen omringd door kleinere stappen . De herhaling suggereert een onderliggende structuur voor de beste oplossingen die nog niemand heeft kunnen verklaren. Maar Grimmer is in ieder geval hoopvol.

"Als ik het niet kan kraken, zal iemand anders het doen," zei hij.