Tight Complexity Bounds for Composite Optimization

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=JRf8xVeNBKw


Duration: 53:53
275 views
4

We provide tight upper and lower bounds on the complexity of minimizing the average of $m$ convex functions using gradient and prox information for the component functions. We show a significant gap between the complexity of deterministic vs randomized optimization. For smooth functions, we show that accelerated gradient descent and an accelerated variant of SVRG are optimal in the deterministic and randomized settings respectively, and that a gradient oracle is sufficient for that optimal rate. For non-smooth functions, having access to prox oracle reduces the complexity and we present optimal methods based on smoothing AGD that improve over methods using just gradient accesses.

See more on this video at https://www.microsoft.com/en-us/research/video/tight-complexity-bounds-composite-optimization/



Other Videos By Microsoft Research


2016-10-25Proxy-guided Image-based Rendering for Mobile Devices
2016-10-25Parallel Poisson Disk Sampling with Spectrum Analysis on Surfaces
2016-10-25Unlock deeper learning with the new Microsoft Cognitive Toolkit
2016-10-21Interactive Sound Synthesis for Large Scale Virtual Environments
2016-10-21Efficient and Accurate Sound Propagation Using Adaptive Rectangular Decomposition
2016-10-21Precomputed Wave Simulation for Real-Time Sound Propagation of Dynamic Sources in Complex Scenes
2016-10-21Wave-Based Sound Propagation in Large Open Scenes using an Equivalent Source Formulation
2016-10-21Parametric Wave Field Coding for Precomputed Sound Propagation
2016-10-20Aerophones in Flatland: Interactive Wave Simulation of Wind Instruments
2016-10-20The FedEx Problem
2016-10-20Tight Complexity Bounds for Composite Optimization
2016-10-17XWand: UI for Intelligent Spaces
2016-10-17Pointing in Intelligent Environments with the WorldCursor
2016-10-13A Neurally-Inspired Model of Habit and its Empirical Implications
2016-10-13Global Education Data on What Drives Student Outcomes
2016-10-13Faculty Summit 2016 - Spatial Audio for Augmented and Virtual Reality
2016-10-12Pictionaire: Supporting Collaborative Design Work by Integrating Physical and Digital Artifacts
2016-10-11GWindows: Robust Stereo Vision for Gesture-Based Control of Windows
2016-10-11TouchLight: An Imaging Touch Screen and Display for Gesture-Based Interaction
2016-10-11PlayAnywhere: A Compact Interactive Tabletop Projection-Vision System
2016-10-11PlayTogether


Tags:
microsoft research