Gradient İnişi ve Optimizasyonun Sırları: Karesel Sandviç
Gradient inişi ile bir fonksiyonu optimize etmeye çalıştıysanız, bazı fonksiyonların optimizasyonun keyifli olduğunu, bazılarının ise bir kabusa dönüştüğünü fark etmişsinizdir. Bu fark genellikle iki temel özelliğe dayanır: güçlü konvekslik ve L-düzgünlük. Bu iki kavram, fonksiyonunuzun etrafında karesel sınırlar oluşturan bir ‘sandviç’ tanımlar ve fonksiyonun ne kadar iyi huylu olduğunu kesin olarak gösterir. Eğer sandviç sıkıysa, hayat güzeldir. Bir dilim ekmek eksikse, işler hızla çirkinleşir.
Bu yazıda, her iki kavramı sıfırdan inceleyecek, karesel sandviçte nasıl birleştiklerini görecek, Hessian’ın özdeğerleri düzeyinde neler olduğunu anlayacak ve L-düzgünlüğünü özdeğer hesaplamadan doğrulamak için harika bir püf noktası öğreneceğiz.
Güçlü Konvekslik: Fonksiyon Asla Çok Düz Olamaz
Diferansiyellenebilir bir $f : \mathbb{R}^{n} \rightarrow \mathbb{R}$ fonksiyonu, $\mu$-güçlü konvekstir (burada $\mu > 0$) eğer tüm $x , y$ için aşağıdaki eşitsizliği sağlıyorsa:
‘f(y) \geq f(x) + \langle \nabla f(x) , y – x \rangle + (\mu/2) \parallel y – x \parallel^{2}’
Bu ifade tanıdık geliyorsa, bunun nedeni sağdaki ilk iki terimin $f$’in $x$ noktasındaki birinci dereceden Taylor açılımı olmasıdır. Sıradan bir konveks fonksiyon için, Taylor açılımı zaten küresel bir alt sınırlayıcıdır (bu, altgradyen eşitsizliğidir). Ancak güçlü konvekslik daha fazlasını ister: fonksiyon, teğetin artı karesel bir boşluk üzerinde kalmalıdır. $\mu$ parametresi bu boşluğun ne kadar agresif olduğunu kontrol eder — $\mu$ ne kadar büyükse, fonksiyon o kadar yukarı doğru ve doğrusal yaklaşımından uzağa doğru kıvrılır.
Sezgisel olarak, güçlü konveks bir fonksiyonun her yönde garantili bir minimum $\mu$ eğriliğine sahip olduğu anlamına gelir. Düzleşemez, plato oluşturamaz, bir yönün temelde düz olduğu dejenere bir vadiye sahip olamaz. Sizi minimuma doğru çeken her zaman bir kuvvet vardır ve bu kuvvet minimumdan uzaklıkla doğrusal olarak büyür.
L-Düzgünlük: Fonksiyon Asla Çok Dik Olamaz
Diferansiyellenebilir bir $f$ fonksiyonu, gradyanı Lipschitz sürekli ise $L$-düzgündür. Bu, aşağıdaki ifadeyle gösterilir:
‘\parallel \nabla f(x) – \nabla f(y) \parallel \leq L \parallel x – y \parallel \forall x , y’
Bu ifadeyi dikkatlice okuyun: herhangi iki nokta arasındaki gradyan değişimi, girişin yeniden ölçeklendirilmiş bir versiyonu tarafından her zaman domine edilir. $x$ ve $y$ ne kadar uzakta olursa olsun, gradyan farkı ‘\parallel \nabla f(x) – \nabla f(y) \parallel’, giriş farkının ‘L’ katını asla aşamaz. Sabit ‘L’ gradyan üzerinde bir tasma görevi görür: hareket edebilir, ancak aniden sarsılamaz. Ani dönüşler veya eğrilikte ani sıçramalar olmaz.
Şimdi sandviç için önemli olacak eşdeğer karakterizasyon, bazen iniş lemmas olarak adlandırılır: Eğer $f$ konveks ve $L$-düzgünse, o zaman tüm $x , y$ için aşağıdaki ifade geçerlidir:
‘f(y) \leq f(x) + \langle \nabla f(x) , y – x \rangle + (L/2) \parallel y – x \parallel^{2}’
Bu, yalnızca Lipschitz koşulundan açık değildir — ekte kısa bir türetme gerektirir. Ana fikir, gradyanı $x$’ten $y$’ye olan segment boyunca entegre etmek ve hatayı kontrol etmek için Cauchy-Schwarz’ı Lipschitz sınırı ile birlikte kullanmaktır.
Yapısına bakın: güçlü konvekslik koşuluyla aynı şekil, ancak eşitsizlik ters çevrilmiş ve $\mu$, $L$ ile değiştirilmiştir. Fonksiyon şimdi teğetinin altında, artı karesel bir terimle kalır. Başka bir deyişle, fonksiyon bükülebilir, ancak $L$ eğriliğine sahip bir kareselden daha fazla bükülemez.
‘L’ parametresi, herhangi bir yöndeki maksimum eğriliği sınırlar. Eğer güçlü konvekslik eğriliğe bir taban belirliyorsa, L-düzgünlük bir tavan belirler.
Karesel Sandviç: İki Sınır Bir Arada
Şimdi iki ekmek dilimini bir araya getirelim. Eğer $f$, $\mu$-güçlü konveks ve $L$-düzgünse, her iki eşitsizlik de aynı anda geçerli olur ve tüm $x , y$ için şunları elde ederiz:
‘f(x) + \langle \nabla f(x) , y – x \rangle + (\mu/2) \parallel y – x \parallel^{2} \leq f(y)’
‘f(y) \leq f(x) + \langle \nabla f(x) , y – x \rangle + (L/2) \parallel y – x \parallel^{2}’
Fonksiyon, herhangi bir $x$ noktasında merkezlenmiş iki parabol arasında sıkışmıştır: alttan daha sıkı bir tanesi (\mu eğriliği) ve üstten daha geniş bir tanesi ($L$ eğriliği). İşte bu karesel sandviçtir.
Koşul Sayısı: Sandviçin Kalınlığı
‘\kappa = L/\mu’ oranı, koşul sayısı olarak adlandırılır ve sandviçin ne kadar kalın olduğunu ölçer. Yapısı gereği, $L \geq \mu$ olduğundan (maksimum eğrilik minimum eğrilikten küçük olamaz), koşul sayısı her zaman 1’den büyük veya eşittir: $\kappa \geq 1$. Küçük bir $\kappa$ (1’e yakın) fonksiyonun ‘neredeyse karesel’ olduğu anlamına gelir — her iki sınır da sıkıdır ve fonksiyonu optimize etmek kolaydır. Büyük bir $\kappa$, eğriliğin yönlere göre büyük ölçüde değiştiği anlamına gelir ve bu noktada gradyan inişi sıkıntı çekmeye başlar. Bunu iki senaryoda düşünün:
- Bazı yönlerde eğrilik eksikliği ($\mu$ çok küçük): Küçük bir $\mu$ ille de fonksiyonun düz olduğu anlamına gelmez — yine de sıfır olmayan bir eğiminiz olabilir. Ancak bu, yararlanacak bir ‘ivme’niz olmadığı anlamına gelir: gradyan bir iterasyondan diğerine zar zor değişir, bu nedenle minimuma yaklaşıp yaklaşmadığınızı veya adım boyutunuzu nasıl ayarlayacağınızı tahmin edemezsiniz. Sabit bir eğimde yürümeyi düşünün — hareket ediyorsunuz, ancak arazi ilerlemeniz hakkında size geri bildirim vermiyor.
- Gradyan çok ani değişir ($L$ çok büyük): Güçlü konvekslik eksikliğinin aksine — burada sorun gradyanın değişmemesidir — burada sorun çok fazla değişmesidir. Birdenbire, bir iterasyondan diğerine, gradyan adım boyutunuzun tahmin etmediği bir şekilde yükselir veya yön değiştirir. Yalnızca büyük bir $L$ tek başına mutlaka felaket değildir: eğer $\mu$ da büyükse (her yerde yüksek eğrilik), fonksiyon sadece dik ama iyi huylu bir kasedir ve tekdüze çalışan küçük bir $1/L$ adım boyutu kullanabilirsiniz.
Asıl sorun, $L$ ve $\mu$ arasındaki farktan kaynaklanır — yani büyük bir koşul sayısı $\kappa = L / \mu$. Fark önemli olduğunda, bazı yönlerde yüksek eğrilik (gradyanın hızlı değiştiği yer) ve diğerlerinde düşük eğrilik (gradyanın neredeyse sabit olduğu yer) bulunur. Tek bir adım boyutu her ikisine de hizmet edemez: yüksek eğriliğe sahip yönler için boyutlandırıldığında düşük eğriliğe sahip olanlar için çok muhafazakardır ve bunun tersi de geçerlidir. Bu uyumsuzluk, gradyan inişinin klasik zikzak çizme davranışına neden olur — bu sadece $L$ veya $\mu$ değil, ikisi arasındaki kötü koşullandırmadır.
$\kappa = 1$ olduğunda (yani $\mu = L$), sandviç mükemmel dengededir: aynı karesel fonksiyon $f$’i hem yukarıdan hem de aşağıdan sınırlar. $f$ iki özdeş parabol arasında sıkıştığından, o parabol olmak zorundadır. Sandviç bir eşitliğe dönüşür: tüm $x , y$ için ‘f(y) = f(x) + \langle \nabla f(x) , y – x \rangle + (\mu/2) \parallel y – x \parallel^{2}’
Fonksiyon, her yerde kendi ikinci dereceden yaklaşımıdır — hata yok, boşluk yok. Şimdi bunu ‘\nabla f(x^{\star}) = 0’ olan minimize edici $x^{\star}$ noktasında değerlendirin:
‘f(y) = f(x^{\star}) + (\mu/2) \parallel y – x^{\star} \parallel^{2}’
Yani $f$, $x^{\star}$ noktasında merkezlenmiş mükemmel karesel bir kasedir. Ancak daha fazlasını sıkıştırabiliriz. Eşitliği $y$’ye göre türevlemek ‘\nabla f(y) = \mu (y – x^{\star})’ verir: herhangi bir noktadaki gradyan, minimize ediciden radyal olarak uzağa işaret eden yeniden ölçeklenmiş bir vektördür. Zikzak çizme, yanlış hizalama yoktur — $1/\mu$ adım boyutuna sahip gradyan inişi, minimuma tam olarak bir adımda ulaşır:
‘y – (1/\mu) \nabla f(y) = y – (y – x^{\star}) = x^{\star}’
Başka bir deyişle, mükemmel sandviçe sahip tek fonksiyonlar karesellerdir ve kareseller, gradyan inişinin hiç yinelemeye ihtiyaç duymadığı tek fonksiyonlardır.
Tek Dilim Ekmek Olmadan Neler Ters Gider?
Güçlü Konvekslik Olmadan
$\mu = 0$ olarak ayarlayın ve alt sınır teğet hiper düzlemine dejenere olur — minimuma doğru karesel çekimi kaybedersiniz. Koşul sayısı $\kappa = L / \mu$, $+ \infty$’a doğru uçar, ki bu ‘gradyan inişinin kötü zaman geçireceği’nin matematiksel ifadesidir.
Güçlü konveksliğin gizli sosu, gradyanın her adımda kayda değer bir şekilde değişmesinin garantilenmesidir. $\mu$-güçlü konveks bir fonksiyon için, ‘\parallel \nabla f(x) \parallel’, ‘\parallel x – x^{\star} \parallel’ ile en azından orantılı olarak büyür: büyük bir gradyan optimumdan uzakta olduğunuzu, küçük bir gradyan ise yakın olduğunuzu gösterir. Her iterasyonda, gradyan normu minimuma ne kadar yakın olduğunuzu tahmin etmenizi sağlar — bu kalibre edilmiş bir sinyaldir. Bunun somut algoritmik sonuçları vardır: kabaca ne kadar uzakta olduğunuzu biliyorsanız, uygun büyüklükte adımlar atabilirsiniz — uzaktayken büyük, yakınken küçük (eğimin ayaklarınızın altında düzgün değiştiğini varsayarsak, ki bu L-düzgünlüğünün garantisidir).
Güçlü konvekslik olmadan, gradyan bu kalibrasyonu kaybeder. $f(x) = \parallel x \parallel_{1}$ fonksiyonunu düşünün: gradyan, orijin dışında her yerde $\pm 1$’dir — size yönü verir ancak mesafeyle ilgili hiçbir şey söylemez. $x = 100$ veya $x = 0.001$ konumunda olsanız da, gradyan aynı yoğunlukta çığlık atar. Hareket ettikçe gradyan hiç değişmez, bu nedenle ilerlemenizi ölçmenin bir yolu yoktur. Huber kaybında da aynı şey olur: doğrusal bölgeye girdiğinizde gradyan sabittir ve yakın mı yoksa uzak mı olduğunuzu söyleyemezsiniz. Mesafeyle ölçeklenen bir gradyan olmadan, çözümleyici kör uçar — minimuma yakınlığa göre adım boyutunu ayarlamanın bir yolu yoktur.
Daha da kötüsü, güçlü konvekslik olmadan, minimize edicinin benzersiz olduğuna dair garantiyi kaybedersiniz. Fonksiyonun bir minimize ediciler alt uzayı veya gradyanın kaybolduğu ancak optimuma hiç yakın olmadığınız düz bir bölgesi olabilir.
L-Düzgünlük Olmadan
Bir hedefe körlemesine bir topa vurduğunuzu hayal edin — sahayı göremiyorsunuz, ancak birisi size vuracağınız yönü söylüyor. Çamurda vurduğunuz sürece hayat tahmin edilebilirdir: top her seferinde biraz hareket eder, sürtünme işleri kontrol altında tutar ve siz her vuruştan sonra nereye düşeceğini makul bir şekilde tahmin edebilirsiniz. Adım adım istikrarlı bir ilerleme kaydedersiniz. Ama şimdi çamurun aniden yok olduğunu ve buz üzerinde olduğunuzu hayal edin. Önceki gibi aynı enerjiyle vuruyorsunuz, ancak bu sefer top uzağa uçar — hedefi aşar ve başladığınız yerden daha da uzağa düşer. Zemin ayaklarınızın altında değişti, ancak vurma gücünüz buna uyum sağlamadı.
L-düzgünlük olmadan temel sorun budur: bir bölgede (gradyanın orta düzeyde olduğu, ‘çamur’) iyi çalışan bir adım boyutu bulursunuz, kendinize güvenerek ilerlersiniz, ancak gradyanın patladığı bir bölgeye (‘buz’) varırsınız — gradyandaki değişim, girdideki değişimden çok daha büyüktü. Aynı adım boyutunu kullanmak şimdi felaketle sonuçlanan bir aşırı atışa neden olur ve başlangıç noktanızdan daha da uzakta bir minimuma düşebilirsiniz.
Matematiksel olarak: üst sınırı kaldırın ve fonksiyon keyfi olarak yükselebilir. Mevcut gradyanına dayanarak bir adım atan bir çözümleyici, yeni noktadaki fonksiyon değerinin ne olacağı konusunda hiçbir garantiye sahip değildir — eğrilik mevcut nokta ile bir sonraki nokta arasında patladığı için beklenenden çok daha yüksek olabilir.
$f(x) = – \ln(x)$ fonksiyonunu $x > 0$ için düşünün: ikinci türev $1/x^{2}$’dir, bu da $x \rightarrow 0$ iken sınırsızdır. Orijinden uzakta fonksiyon naziktir ($x = 10$’da eğrilik sadece $0.01$’dir), ancak orijine yakın eğrilik patlar ($x = 0.1$’de eğrilik $100$’dür). Nazik bölge için kalibre edilmiş bir adım boyutu, sizi dik bölgeye taşırsa büyük ölçüde aşırı atış yapar ve dik bölge için yeterince muhafazakar bir adım boyutu, her yerde sürünür.
$f(x) = \parallel x \parallel$ gibi türevlenemeyen bir fonksiyonun aşırı durumunda, gradyan kırılma noktasında anında değişir — o noktada etkili $L$ sonsuzdur. Standart gradyan inişi, değişiklik yapmadan bunu basitçe ele alamaz.
Her İki Özellik de Önemli
Aslında, her iki özelliği birlikte anlamanın doğru yolu budur: güçlü konvekslik, optimizasyon yolu boyunca yerel bilginin ne kadar zengin olduğuyla ilgilidir — gradyanın her iterasyonda anlamlı bir şekilde değişmesini, konumunuz hakkında yararlı sinyallerle yoğun olmasını sağlar. L-düzgünlük ise bu yerel bilginin ne kadar güvenilir olduğuyla ilgilidir — manzaranın çok ani değişmemesini sağlar, böylece bir adım için yerel gradyanlara güvenmek sizi beklenmedik bir yere götürmez. İyi koşullandırılmış bir problem her ikisine de sahiptir: bol ve güvenilir yerel bilgi.
Spektral Bakış Açısı: Hessian’ın Özdeğerlerini Okumak
Eğer $f$ iki kez türevlenebilirse, tartıştığımız her şey Hessian $\nabla^{2} f(x)$’ten okunabilir. $f$ konveks olduğundan, Hessian her noktada pozitif yarı kesinlik gösterir, bu da tüm özdeğerlerinin negatif olmayan olduğu anlamına gelir:
‘0 \leq \lambda_{1}(x) \leq \lambda_{2}(x) \leq \hdots \leq \lambda_{n}(x)’
Her özdeğer $\lambda_{i}(x)$, bir özvektör $v_{i}(x)$ ile eşleştirilir — Hessian’ın basit ölçeklendirme ile etki ettiği bir $\mathbb{R}^{n}$ yönü: ‘\nabla^{2} f(x) v_{i}(x) = \lambda_{i}(x) v_{i}(x)’. Eğer $x$’te durup $v_{i}$ boyunca $\epsilon$ boyutunda küçük bir adım atarsanız, ikinci dereceden Taylor açılımı şunu verir:
‘f(x + \epsilon v_{i}) \approx f(x) + \epsilon \langle \nabla f(x), v_{i} \rangle + (\lambda_{i}(x)/2) \epsilon^{2}’
Yani, özvektör $v_{i}$ boyunca hareket ederseniz, Hessian’ın $f$’deki değişime katkısı $\lambda_{i}(x)$ tarafından yönetilir: büyük bir özdeğer, fonksiyonun o yönde keskin bir şekilde büküldüğü anlamına gelirken, küçük bir özdeğer, neredeyse düz olduğu anlamına gelir. Özvektörler, her noktada bir dizi ‘doğal eksen’ tanımlar ve özdeğerler, bu eksenlerin her biri boyunca eğriliği söyler.
Spektrum Aracılığıyla Güçlü Konvekslik
Güçlü konvekslik, en küçük özdeğerin her yerde sıfırdan uzak kalması anlamına gelir:
‘\lambda_{1}(x) \geq \mu > 0 \forall x’
Eğer tek bir özdeğer bir noktada sıfıra dokunursa, o yönde eğriliği kaybetmiş olursunuz — fonksiyonun o noktada ‘düz bir yönü’ vardır ve güçlü konvekslik başarısız olur. $\mu$ parametresi en sıkı bu tür sınırdır: $\mu = (\inf)_{x} \lambda_{1}(x)$. $\mu = 0$ olduğunda, sandviçten gelen karesel alt sınır teğet hiper düzlemine dejenere olur: fonksiyonun herhangi bir noktadan uzaklaştığını artık garanti edemezsiniz, bu da minimize edicinin benzersiz olmayabileceği (veya hiç var olmayabileceği) anlamına gelir. Taylor açılımına geri dönersek, eğer $\lambda_{i}(x) \approx 0$ ise, ikinci dereceden terim ‘( \lambda_{i}/2) \epsilon^{2}’ esasen yok olur: $v_{i}$ boyunca hareket etmek fonksiyonun değerini zar zor değiştirir, bu nedenle manzara o yönde neredeyse düzdür. Gradyan inişi için bu, gradyanın $v_{i}$ boyunca nasıl hareket edileceği hakkında neredeyse hiç bilgi taşımadığı anlamına gelir — o yönde esasen körsünüzdür. $\lambda_{i}(x) = 0$ olduğu aşırı durumda, ‘\nabla^{2} f(x) v_{i} = 0’ olur, bu da $v_{i}$’nin Hessian’ın çekirdeğine ait olduğu anlamına gelir. ‘ker(\nabla^{2} f(x))’nin boyutu, $x$’te kaç bağımsız yönün tamamen ‘ölü’ olduğunu söyler — hiç eğrilik yoktur. Tek boyutlu bir çekirdek tek bir düz yöndür; büyük bir çekirdek, fonksiyonun birçok yönde aynı anda dejenere olduğu anlamına gelir. Dolayısıyla, Hessian’ın çekirdeğini incelemek, güçlü konveksliğin belirli bir noktada ne kadar ciddi şekilde ihlal edildiğinin doğrudan bir ölçüsünü verir.
Spektrum Aracılığıyla L-Düzgünlük
L-düzgünlük, en büyük özdeğerin her yerde yukarıdan sınırlı olması anlamına gelir:
‘\lambda_{n}(x) \leq L \forall x’
$L$ parametresi en sıkı bu tür sınırdır: $L = (\sup)_{x} \lambda_{n}(x)$. Bu sınır başarısız olduğunda — yani $\lambda_{n}(x)$ sınırsız olduğunda — sonlu bir $L$ yoktur ve fonksiyon düzgün değildir.
Bunun somut olarak ne anlama geldiğini görmek için Taylor açılımına geri dönün. En büyük özdeğerle ilişkili özvektör $v_{n}$ boyunca ikinci dereceden terim ‘( \lambda_{n}(x)/2) \epsilon^{2}’dir. Eğer $\lambda_{n}(x)$ çok büyükse, $v_{n}$ boyunca küçücük bir $\epsilon$ adımı bile fonksiyon değerinde büyük bir değişikliğe neden olur — manzara o yönde son derece diktir. Daha nazik yönler için kalibre edilmiş bir adım boyutu seçen bir çözümleyici, $v_{n}$ boyunca büyük ölçüde aşırı atış yapar.
Ancak asıl sorun, $\lambda_{n}(x)$’nin sadece büyük olması değil, aynı zamanda alan boyunca dramatik bir şekilde değişmesidir. $f(x) = x^{4}$ fonksiyonunu düşünün: ikinci türev $12x^{2}$’dir, bu orijine yakın neredeyse sıfırdır ancak $\parallel x \parallel$ büyüdükçe patlar. $x = 0$’da Hessian ‘fonksiyon düz, büyük bir adım atın’ der; $x = 10$’da Hessian ‘fonksiyon 1200 oranında eğriliyor, dikkatli olun’ der. Hiçbir tek $L$ bu fonksiyonun eğriliğini her yerde doğru bir şekilde tanımlayamaz ve küresel bir $1/L$ adım boyutuna güvenen bir çözümleyici ya pervasız (eğer $L$ çok küçükse) ya da aşırı çekingendir (eğer $L$ en kötü durumu karşılayacak şekilde ayarlanmışsa).
En aşırı senaryoda, eğer bir $x$ noktasında $\lambda_{n}(x) \rightarrow \infty$, sandviçten gelen karesel üst sınır geçersiz hale gelir: hiçbir sonlu parabol fonksiyonu yukarıdan sınırlayamaz. İniş lemmas’ı çöker ve çözümleyicinin bir adımdan sonra ne olacağına dair güvenilir bir modeli yoktur — tıpkı topu buz üzerinde tekmelemek gibi, çözümleyicinin nereye düşeceğine dair hiçbir fikri yoktur.
Genel olarak, Hessian’ı bir özvektöre uygulamak, aynı özvektörü ilgili özdeğerle yeniden ölçeklenmiş olarak döndürür: ‘\nabla^{2} f(x) v_{i} = \lambda_{i}(x) v_{i}’. Özdeğer, yeniden ölçekleme faktörüdür. Şimdi, $\mu$ ve $L$ spektrumun sınırlarını tanımlar: her noktadaki ‘\nabla^{2} f(x)’in tüm özdeğerleri ‘[ \mu , L ]’ aralığında bulunmalıdır, bu da tüm bu yeniden ölçekleme faktörlerinin bu aralığa hapsedildiği anlamına gelir. Bu aralığın genişliği — nihayetinde $\kappa = L / \mu$ ile yakalanan — Hessian’ın farklı yönleri yeniden ölçeklemesinde ne kadar değişkenlik olduğunu söyler.
$\kappa$ 1’e yakın olduğunda, ‘[ \mu , L ]’ aralığı sıkıdır: her özvektör, Hessian ile çarpıldığında yaklaşık olarak aynı yeniden ölçeklemeyi alır (çünkü özdeğerler benzerdir). Hessian’a genel bir vektör $d$ uygulamak, büyüklüğü tahmin edilebilir bir sonuç üretir — $d$’nin hangi yöne işaret ettiğinin çok fazla önemi yoktur, çünkü tüm yönler neredeyse eşit şekilde ele alınır. Hessian elipsi ‘{ $d : d^{\top} \nabla^{2} f(x) d \leq 1$ }’ neredeyse küreseldir ve gradyan inişi iyi çalışır.
$\kappa$ büyük olduğunda, ‘[ \mu , L ]’ aralığı geniştir: farklı özvektörler büyük ölçüde farklı yeniden ölçeklemeler alabilir. $\lambda_{n}$’nin özvektörüyle hizalanmış bir yön $L$ ile yükseltilirken, $\lambda_{1}$’in hizalanmış bir yönü zar zor ölçeklenir. Tipik olarak özvektörlerin bir karışımı olan herhangi bir genel yön, bileşenlerinin çok farklı faktörlerle gerilmesine neden olacaktır. Hessian’ın eylemi son derece anizotropik hale gelir: bir vektörü ona uygulamanın sonucu, o vektörün nereye işaret ettiğine dramatik bir şekilde bağlıdır. Elips uzar ve gradyan inişi zikzak çizer çünkü gradyan (optimumdan yer değiştirmeye uygulanan Hessian) minimuma giden gerçek yönü sistematik olarak yanlış temsil eder.
Somut bir örnek olarak, $f(x) = (1/2) x^{\top} H x$ şeklinde bir karesel fonksiyon düşünün, burada $H = \text{diag} ( \mu , L )$. Hessian her yerde $H$’dir, bu nedenle elipsin yarı eksenleri $1/\sqrt{\mu}$ ve $1/\sqrt{L}$ uzunluğundadır ve eksantriklik oranı $\sqrt{\kappa}$’dır.
Doğrulama Hilesi: Özdeğer Hesaplamadan
Hessian’ın özdeğerlerini kapalı formda hesaplamak her zaman mümkün değildir. Neyse ki, hem L-düzgünlüğü hem de güçlü konveksliği kontrol etmek için soruyu basit konveksliğe indirgeyen zarif bir kısayol vardır — bu genellikle doğrulanması daha kolaydır.
İddia. $f$, aşağıdaki fonksiyon konveks ise ve ancak o zaman $L$-düzgündür:
‘g(x) = (L/2) \parallel x \parallel^{2} – f(x)’
Neden Çalışır? Eğer $f$ iki kez türevlenebilirse, $g$’nin Hessian’ı şudur:
‘\nabla^{2} g(x) = L I – \nabla^{2} f(x)’
Bu matris, eğer ‘\nabla^{2} f(x)’in her özdeğeri en fazla $L$ ise ve ancak o zaman PSD’dir, ki bu tam olarak L-düzgünlük için spektral koşuldur. Dolayısıyla ‘g konveks mi?’ kontrol etmek, ‘f’nin tüm Hessian özdeğerleri $L$ ile sınırlı mı?’ kontrol etmekle aynıdır.
Simetrik olarak, $f$, aşağıdaki fonksiyon konveks ise ve ancak o zaman $\mu$-güçlü konvekstir:
‘h(x) = f(x) – (\mu/2) \parallel x \parallel^{2}’
$h$’nin Hessian’ı ‘\nabla^{2} f(x) – \mu I$’dir, bu da eğer ‘\nabla^{2} f(x)’in her özdeğeri en az $\mu$ ise ve ancak o zaman PSD’dir.
Aşağıdaki tabloyu kontrol edin: iki yardımcı fonksiyon sadece $\mu \leq 1$ ve $L \geq 3$ olduğunda konveks hale gelir.
Sonuç
İşte ele aldıklarımız:
- Güçlü konvekslik karesel bir alt sınır garantisi verir: fonksiyon, minimum $\mu$ eğriliği ile teğetinden uzaklaşır.
- L-düzgünlük karesel bir üst sınır garantisi verir: fonksiyon $L$’den daha hızlı eğrilemez.
- Birlikte, iki sınırın karesel boşlukları arasındaki göreceli mesafeyi temsil eden koşul sayısı $\kappa = L / \mu$ tarafından kontrol edilen karesel sandviçi oluştururlar.
- Spektral düzeyde, bu özellikler Hessian özdeğerleri üzerinde küresel sınırlara karşılık gelir: ‘$\mu \leq \lambda_{i}(x) \leq L$’.
- Doğrulama hilesi, bu özellikleri kontrol etmeyi değiştirilmiş bir fonksiyonun basit konveksliğine indirger.
Bu iki özellik, optimizasyon teorisindeki en önemli yapısal varsayımlardan ikisidir. Gradyan inişinin bazı problemlerde iyi, bazılarında ise korkunç çalışmasının nedeni onlardır ve koşul sayısı $\kappa$, düzgün konveks bir problemin zorluğunu en iyi özetleyen tek sayıdır.
Ancak burada daha derin bir hikaye gizlidir. Güçlü konvekslik ve L-düzgünlük bağımsız kavramlar değildir — Fenchel eşleniğini içeren kesin bir anlamda birbirlerinin çiftidirler. Eğer bu size önceki bir yazıdan tanıdık geliyorsa, beklemede kalın.
Bu arada, unutmayın: iyi dengelenmiş bir sandviç, sağlıklı bir yaşamın anahtarıdır — ister karesellerden ister tam tahıllı ekmekten yapılmış olsun. İyi yiyin, iyi optimize edin.
