BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Frederik Kunstner (UBC) DTSTART:20231130T220000Z DTEND:20231130T230000Z DTSTAMP:20260513T193650Z UID:SFUOR/27 DESCRIPTION:Title: S earching for Optimal Per-Coordinate Step-sizes with Multidimensional Backt racking\nby Frederik Kunstner (UBC) as part of PIMS-CORDS SFU Operatio ns Research Seminar\n\nLecture held in ASB 10908.\n\nAbstract\nThe backtra cking line-search is an effective technique to automatically tune the step -size in smooth optimization. It guarantees similar performance to using t he theoretically optimal step-size. Many approaches have been developed to instead tune per-coordinate step-sizes\, also known as diagonal precondit ioners\, but none of the existing methods are provably competitive with th e optimal per-coordinate stepsizes. We propose multidimensional backtracki ng\, an extension of the backtracking line-search to find good diagonal pr econditioners for smooth convex problems. Our key insight is that the grad ient with respect to the step-sizes\, also known as hypergradients\, yield s separating hyperplanes that let us search for good preconditioners using cutting-plane methods. As black-box cutting-plane approaches like the ell ipsoid method are computationally prohibitive\, we develop an efficient al gorithm tailored to our setting. Multidimensional backtracking is provably competitive with the best diagonal preconditioner and requires no manual tuning.\n LOCATION:https://researchseminars.org/talk/SFUOR/27/ END:VEVENT END:VCALENDAR