אופטימיזציה דו-רמתית (עליונה לא קמורה, תחתונה קמורה בחוזקה) כמעט-מיטבית עם אורקלים מדרגה ראשונה (גרדיאנט) בלבד

המאמר נותן כלי פרקטי ללימוד היפרפרמטרים, ניקוי מידע ואימון ביילבלי של מודלים גדולים מבלי להזדקק לחישוב מוצרי הייסיאן יקרים; זאת מאפשרת החלה קלה יותר במערכות מבוזרות ורשתות ענק בהן חישוב HVP יקר או בלתי נגיש., האלגוריתם והשכלולים הסטוכסטיים מאפשרים יישום בעבודה של אימון מודלים על נתונים רעשים או בשיטות reweighting לדאטה מטוהרת, שם רוצים ללמוד משקלים לדוגמאות או משאבים ללא עלות חישובית גבוהה., גרסת ההאצה והגרסה המפריעה מספקות מנגנונים שניתנים לשילוב במערכות פיתוח ואופטימיזציה כדי להימנע מהיתקעות בנקודות אוכף או בסדל-פוינטס ולשפר את קצב ההיתכנות המקומלית של תוצאות האימון.

רקע ובעיית המחקר, המאמר עוסק בבעיית האופטימיזציה הביילבלית הקלאסית שבה המטרה העליונה תלויה בפתרון של בעיית המשנה התחתונה. יוצא הדופן במחקר הוא המקרה שנחקר: הפונקציה העליונה עשויה להיות לא-קמורה ואילו התחתונה היא חזקה-קמורה. בתרחיש זה קיימת הופעה של גרדיאנט היפר (hypergradient) שמערב אינברסיה של המטריצת הייסיאן של הבעיה התחתונה; שיטות קיימות רבות מנצלות מכשירי HVP (Hessian-Vector Product) כדי לקבל אומדנים מדויקים של הגרדיאנט העליון ולהשיג קצב התכנסות של Õ(ε^{-2})., ### המגבלה המעשי של HVP והשאילתא המחקרית, למרות יעילותן התיאורטית, קריאות HVP עלולות להיות יקרות או בלתי נגישות ביישומים פרקטיים כגון אימון מודלים גדולים או הפצות מחושבות. עבודות קודמות הציעו שיטות מבוססות גרדיאנט בלבד אך סבלו מקומפלקסיות גרועה יותר (למשל Õ(ε^{-3})). המחבריוים שואלים האם ניתן לגשר על הפער הזה ולשחזר את קצב ה-Õ(ε^{-2}) תוך שימוש אך ורק באורקל גרדיאנט ראשון., ### רעיון מרכזי ושיטת F2BA, התרומה המרכזית היא פיתוח האלגוריתם Fully First-order Bilevel Approximation (F2BA). הרעיון הבסיסי הוא להמיר את הבעיה הביילבלית לשיטה עונשין דרך פונקציית הערך L{λ}(x) = min_y L{λ}(x,y) עם L_{λ} = f + λ(g - g_), ולבצע אופטימיזציה ישירה של L_{λ} באמצעות עדכוני גרדיאנט ראשוניים בלבד. מפתח ההישג הוא שימוש במספר קצבי למידה שונים (two-time-scale): קצב למידה זעיר ל-y ותיקון מהיר ל-x. הבחירה המתאימה של פרמטר העונש λ ושל מהירות העדכונים מבטיחה כי הלנדסקייפ של L{λ} מבחינת חלק ה-x נשאר חלק דומה לזה של פונקציית ה-hyperobjective ϕ(x), ולכן אפשר לבצע עדכוני x בגודל כלשהו מבלי לשלם את מחיר ה-dependency על λ., ### תוצאות תיאורטיות עיקריות, במקרה הדטרמיניסטי הראתה העבודה כי F2BA מוצא נקודת ε-סטציונריות של ϕ(x) במספר אצוות של קריאות גרדיאנט ראשון Õ(ε^{-2}) — כלומר קצב near-optimal התואם לשיטות HVP. הניתוח מצביע ש-L*{λ} מתנהגת כמו ϕ(x) עבור λ גדול מספיק: מרחק ביןagradients של שתי הפונקציות הוא O(1/λ) ושאיפת Hessian/ליפשיץ של ∇^2 L*_{λ} נשלטת ומבוססת על תנאי הבעיה ולא על λ. בעזרת בחירה מתאימה של K(inner steps) ופרמטרים נוספים מתקבל קיזוז שמעניק קצב זה., ### הרחבות סטוכסטיות, המחברים מפתחים גם גרסה סטוכסטית בשם F2BSA ומוכיחים קבלת קצב של Õ(ε^{-4}) במצב שבו רעש סטוכסטי קיים רק ברמה העליונה ובקצב Õ(ε^{-6}) כאשר רעש מופיע בשתי רמות. עוד הם מציעים טכניקה להחלפה של אצוות גדולות (multi-level Monte Carlo) כדי להסיר את הצורך ב-batch-ים מאד גדולים ולשמר את הקומפלקסיות במובן של SFO תוך שמירה על תחזוקת ה-bias/variance., ### בריחה מסיידל-פוינט ושיכלולים מתקדמים, בהנחת חלקיות חלקית (Hessian-Lipschitz ודרגות גזירה גבוהות יותר), המחברים מראים שאפשר להוסיף רעש מבוקר (perturbation) כדי להימנע מהיתקעות בסאדל-פוינט ולקבל ϵ-second-order stationary points תוך אותו סדר גודל של קריאות גרדיאנט. בנוסף, בשימוש בטכניקות האצה דומות לאלו של Nesterov ושיטות מודרניות לאימון לא-קמורות מואצות, הם מפתחים גרסת AccF2BA שמגיעה ל-Õ(ε^{-1.75})., ### ניסויים והדגמות, המאמר כולל ניסויים על בעיות סימולציה וקנה מידה גבוהה: התאמת רגולוריזציה באתגרי רגרסיה ולוגיסטיקה וכן בעיה של data hyper-cleaning באימון GPT-2 על מסדי נתונים עם שגיאות. התוצאות המעשיות מדגימות ש-F2BA וגרסתה המואצת מתמרנות מהר יותר ומשיגות ביצועים טובים יותר מאשר שיטות גרדיאנט חד-זמניות קודמות ולפעמים אף מעל שיטות HVP במקרים בהם ההיפר-מטריצה קרובה לסינגולריות., ### מגבלות וכיווני המשך, למרות השיפורים, המחקר מותיר כמה שאלות פתוחות: האם ניתן להסיר לחלוטין את גורמי הלוגריתם O(log(1/ε)) אל מול Lower bounds ותקרות הדיפנדנסי בתנאי רעש מלא; הרחבה למקרי קונסטריינטים, שיטות single-loop יותר פרקטיות, והבהרת הגבולות התיאורטיים בשלב הסטוכסטי. כמו כן, יישום בחומרה מבוזרת ומצבים בהם לגישה ל-HVP אין עדיין חלופה מעשית צריכים לבחינה נוספת., ### סיכום, המחקר מספק טכניקה פשוטה יחסית אך חזקה לשלב בין אופטימיזציה ביילבלית וביצועים תיאורטיים-פרקטיים ברמה של שיטות המשתמשות במידע שני-סדר, ובכך מצמצם את הפער בין תאוריה לפרקטיקה ומאפשר שימוש נרחב יותר בשיטות ביילבליות בסביבות בהן חישוב HVP בעלות גבוהה או בלתי אפשרי.