Effective performance of neural networks depends critically on effective tuning of optimization hyperparameters, especially learning rates (and schedules thereof). We present Amortized Proximal Optimization (APO), which takes the perspective that each optimization step should approximately minimize a proximal objective (similar to the ones used to motivate natural gradient and trust region policy optimization). Optimization hyperparameters are adapted to best minimize the proximal objective after one weight update. We show that an idealized version of APO (where an oracle minimizes the proximal objective exactly) achieves global convergence to stationary point and locally second-order convergence to global optimum for neural networks. APO incurs minimal computational overhead. We experiment with using APO to adapt a variety of optimization hyperparameters online during training, including (possibly layer-specific) learning rates, damping coefficients, and gradient variance exponents. For a variety of network architectures and optimization algorithms (including SGD, RMSprop, and K-FAC), we show that with minimal tuning, APO performs competitively with carefully tuned optimizers.
I raised my rating. After the rebuttal.
- the authors address most of my concerns.
- it's better to show time v.s. testing accuracy as well. the per-epoch time for each method is different.
- anyway, the theory part acts still more like a decoration. as the author mentioned, the assumption is not realistic.
-------------------------------------------------------------
This paper presents a method to update hyper-parameters (e.g. learning rate) before updating of model parameters. The idea is simple but intuitive. I am conservative about my rating now, I will consider raising it after the rebuttal.
1. The focus of this paper is the hyper-parameter, please focus and explain more on the usage with hyper-parameters. 
- no need to write so much in section 2.1, the surrogate is simple and common in optimization for parameters. After all, newton method and natural gradients method are not used in experiments.
- in section 2.2, please explain more how gradients w.r.t hyper-parameters are computed. 
2. No need to write so much decorated bounds in section 3. The convergence analysis is on Z, not on parameters x and hyper-parameters theta. So, bounds here can not be used to explain empirical observations in Section 5. 
3. Could authors explain the time complexity of inner loop in Algorithm 1? Does it take more time than that of updating model parameters?
4. Authors have done a good comparison in the context of deep nets.  However,
- could the authors compare with changing step-size? In most of experiments, the baseline methods, i.e. RMSProp are used with fixed rates. Is it better to decay learning rates for toy data sets? It is known that SGD with fixed step-size can not find the optimal for convex (perhaps, also simple) problems. 
- how to tune lambda? it is an important hyper-parameter, but it is set without a good principle, e.g., "For SGD-APO, we used lambda = 0.001, while for SGDm-APO, we used lambda = 0.01", "while for RMSprop-APO, the best lambda was 0.0001". What are reasons for these?
- In Section 5.2, it is said lambda is tuned by grid-search. Tuning a good lambda v.s. tuning a good step-size, which one costs more?