Online Control for Meta-optimization
Authors: Xinyi Chen
Elad Hazan
Venue: NeurIPS 2023 spotlight (2023)
Keywords: online learning
control
hyperparameter optimization

Abstract: Choosing the optimal hyperparameters, including learning rate and momentum, for specific optimization instances is a significant yet non-convex challenge. This makes conventional iterative techniques such as hypergradient descent \cite{baydin2017online} insufficient in obtaining global optimality guarantees.

We consider the more general task of meta-optimization -- online learning of the best optimization algorithm given problem instances, and introduce a novel approach based on control theory. We show how meta-optimization can be formulated as an optimal control problem, departing from existing literature that use stability-based methods to study optimization. Our approach leverages convex relaxation techniques in the recently-proposed nonstochastic control framework to overcome the challenge of nonconvexity, and obtains regret guarantees vs. the best offline solution. This guarantees that in meta-optimization, we can learn a method that attains convergence comparable to that of the best optimization method in hindsight from a class of methods.

Online Control for Meta-optimization
Xinyi Chen
Elad Hazan
Princeton University Google DeepMind xinyic@princetoon.edd
Princeton University
Google DeepMind eha ehazzan@princetonnee edu
Abstract
Choosing the optimal hyperparameters, including the learning and momentum, for specific optimization instances a significant yet nonconvex challenge. This makes conventional iterative techniques such hypergradient descent insufficient in obtaining global optimality guarantees in general.
We consider the more general task of meta meta-optimizztion online learning of the best optimization algorithm given problem instances. For this task, a novel approach based on control theory is introduced. We show how meta-optimization can be formulated an optimal control problem, departing from existing literature that use stability-baae -based methods to study optimization. Our approach leverages convex nonstochastic control framework
relaxation techniques in the recently-proposse overcome the challenge of nonconvexity, and obtains regret guarantees vs. the best offline solution. This guarantees that in meta-optimization, we can learn a method that attains convergence comparable that of the best optimization method in hindsight from a class methods.
1 Introduction
The performance of optimization methods, in particular for the application of training deep neural networks, crucially depends on their hyperparameters. [Bengio| [0122] notes that the learning rate the "single most important parameter" for efficient training. However, this parameter is also notoriously hard to tune without intensive hyperparameter search. An even more difficult problem adapting all aspects of an optimization algorithm, including momentum, preconditioner, weight decay, and more, to potentially changing tasks. This is the motivating problem of our paper.
The problem of learning the best optimizer, even for the special case of hyperparameter tuning of the learning rate, is difficult because optimizing these hyperparameters is nonconvex. We tackle this challenging problem by novel framework that based on several components:
We formalize the problem of "finding the best algorithm" as the task of meta-optimization. In this task, the player is given sequence of optimization problems. Her goal is solve them as fast as the best algorithm in hindsight from family of possible methods. This setting generalizes hyperparameter tuning encompass several attributes, including the preconditioning matrix and momentum.
We propose a new metric for meta optimization called meta-regret, which measures the total cost compared to the cost of the best algorithm in hindsight in meta-optimization. We give an efficient method for minimizing the meta-regret that attains sublinear guarantee, which is tight. The implication of this efficient method with optimal meta-regret bound is that we can compete with the best hyperparameters in hindsight (although not necessarily find them).
We give novel control formulation for meta-optimization based on the recently proposed framework of online nonstochastic control. This control formulation differs in several
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

aspects to previous control methods applied to optimization: it is based on optimal control (rather than Lyapunov stability), and requires robustness nonstochastic perturbations.
The online control formulation gives rise our efficient method which is based on the Gradient Perturbation Controller (GPC), a new type online feedback-loop controller that requires only gradient access from the objective functions.
While the method itself is based on recent advancements in control, its analysis requires new technical components. Meta-optimization requires learning between optimization episodes, which necessitates the analysis of feedback control in changing environments without bounded disturbances. This presents a challenge of bounding the magnitude of the state, which we address for the first time in the online control literature.
1.1 The setting of meta-optimization
In meta-optimization, we are given sequence of optimization problems, called episodes. The goal of the player is not only to minimize the total cost in each episode, but also to compete with a set of available optimization methods.
Specifically, each of the N episodes, we have a sequence T optimization steps that are either deterministic, stochastic, online. Throughout the paper, use (t, i) denote time t in episode i. At the beginning of an episode, the iterate is "reset" to given starting point ø1,5. In the most general formulation of the problem, time (1, an optimization algorithm A chooses point æi, K. in convex domain K. C Rd. It then suffers cost (xt,( Let (AA) denote the point chosen by A time (t, i), the protocol of this setting formally defined in Algorithm |
Algorithm 1 Meta-optimization
1: Input: N, T, A. K, reset points {21,))=11
2: for = 1,...., N do
3: fort = 1art=1.....5 do
4:
Play zt,; A(fi,,....., 5: Receive fe, pay (1,(
E Kiitt 1; else play 21,5-
6: end for
7:
end for
The standard goal in optimization, either deterministie, stochastic, online, is minimize the cost of each episode in isolation. In meta-optimization, the goal is to minimize the cumulative cost in both each episode, and overall in terms the choice of the algorithm. We thus define meta-regret be
MetaRegret(AA -A)=E feila,,
Σ (A)))) A'Ell
min
where II is the benchmark algorithm class. The meta-regret is the regret incurred for learning the best optimization algorithm in hindsight, and captures both efficient per-episode optimization as well as competing with the best algorithm in II.
Meta-regret can be studied under various optimization settings. In the deterministic setting, the objectives are the same across time steps and episodes; the stochastic setting. the objectives are drawn from distributions that can vary each t; finally, in the adversarial setting, the objectives appear online. Meta-regret guarantees can be refined for each setting; for example, in the deterministic setting, meta-regret translates bound on the cost of the average iterate.
Why is meta-optimization hard? is natural to apply standard techniques from optimization, such local search or gradient based methods, to meta-optimization. Indeed, this has been studied in numerous previous works under related settings, e.g. [aydin et al. [2077] Chandra et al. 2019].
However, the resulting optimization problem is nonconvex and local gradient optimization may reach suboptimal solutions. For example, a natural application of meta-optimization is learn hyperparamters of class of optimization algorithms. In particular, finding the optimal gradient descent learning rate for a specific objective takes the form the following minimization problem:
min f (xrr, subject to r++1 = Vf))).
7

---

We can unroll the minimization objective from the initial point 21,
f(xr)= = (V) Σ vf()))) = - -VV//) -V/((1 -...
From this expression, it clear that f(r)) a nonconvex function of 17.
The setting of opttaiittiiiiioonn relates to and/or generalizes previous approaches for hyperparamter tuning in optimization. For example, it is the online learning analogue of the average analysis
framework of optimization algorithms [Pedregosa and Scieur 2020 Paquette et al., 202T], and
generalizes control-based approaches for analyzing single optimization instance
Lessard al.
2016
Casgrain and Kratsios 2021
1.2
Main theorem statements
Applying iterative optimization methods directly to the meta-optimization problem is unlikely to result in global guarantees, since the problem is nonconvex. We take a different approach: we formulate meta-optimization an online optimal control problem. Since the control formulation has disturbances that are not stochastic, nonstochastic control framework, and use techniques therein to develop efficient methods for uncon- strained cettaappimiz of quadratic and convex smooth functions.
shown in Section 2 we adopt the recently-develope
The following informal statements of our results, where the algorithm referenced is detailed in Section Due to space constraints, we include the bandit algorithm in Appendix D
Theorem 1.1 (Informal). For quadratic losses, Algorithm satisfies
Meta ΣΣ (a(
min
ΣΣ -
A-Ell
Theorem 1.2 (Informal). For convex smooth losses, bandit variant of Algorithm 2 satisfies
E M = - Ö((NT)314)
In both statements, Ô hides factors polynomial in parameters of the problem and logarithmic T, N. The sublinear scaling in both N and T' implies that with more episodes, the average performance approaches that of the best optimizer from a family of optimization methods in hindsight. Our theorem holds for the most general optimization setting, the adversarial setting where ft, appears in an online fashion. The theorem can be refined for the deterministic and stochastic settings, for more details see Appendix
1.3 Related Work
Online convex optimization and nonstochastic control. Our methods for meta-optimization are based on iterative gradient (or higher order) methods with provable regret guarantees. These have been developed in the context of the online convex optimization framework. In this framework, decision maker iteratively chooses a point 2; E K. for a convex set in Euclidean space K. C Rd. and receives loss according to convex loss function f. K. + R. The goal of the decision maker is to minimize her regret, defined as
T Regret Σ f((2)) min Σ f(()). zEK t=1
T
Notably, the best point x* E IC is defined only in hindsight, since the f. 's are unknown priori. For more information this setting as well algorithmic treatment (Hazan al. 2016
Techniques from online convex optimization were instrumental in developing an online control theory that permits nonstochastic disturbances and is regret-based. Deviating from classical control theory,

---

the online nonstochastic control framework treats control as an interactive optimization problem. where the objective to make decisions that compete with the best controller in hindsight. For a detailed exposition see [[azaa and Singh 2022]. In general, computing the best controller in hindsight a nonconvex optimization problem if we allow general convex costs. However, online nonstochastic control has provable guarantees in this setting despite the nonconvexity, since it uses policies in a larger policy class via convex relaxation. This is crucial for our guarantees: meta- optimization can be a nonconvex problem, but we can hope to use feedback control to bypass the nonconvexity and obtain meta-regret bounds.
Average case analysis of optimization. A closely related framework for analyzing optimization methods is the average-case analysis framework developed in [[eedreoosa and Scieur 2020]. This framework studies the expected performance of optimization algorithms when the problem is sampled from a distribution, and allows for more fine-grained results than typical worst-case analysis. Average- case optimal first-order methods for minimizing quadratic objectives are proposed in [Pedregosa and Scieur 2020]. and (Domingo-Enriee meta-optimization setting is relevant to, but significantly more general than the average-case analysis framework, since we do not assume known stochastic distribution of the optimization problems, and we compete with the best algorithm hindsight.
et al. 202T] extends the study to bilinear games. The
Hypergradient descent and hyperparameter tuning for optimizer parameters. Hyperparameter optimization is a significant problem in deep learning practice, and thus was intensively studied. The work of (aydin al. 2017] apply local iterative methods the problem of optimizing the learning rate from an empirical standpoint, and (Chandra et al. 2019] gives better practical methods. However, even the simple case of optimizing the learning rate can be nonconvex, and it unlikely that iterative methods will yield global optimality guarantees. Certain provable guarantees for quadratic functions and scalar learning rate are presented in [Wang et al. 2021b].
Control for optimization. The connections between control and optimization go back to Lya- punov's 's work and its application to the design and analysis of optimization algoriths. We survey the various approaches in detail in Appendices and Lessard al. (2016] apply control theory the analysis of optimization algorithms on a single problem instance. They give a general framework, us- ing the notion of Integral Quadratic Constraints from robust control theory, for obtaining convergence guarantees for variety of gradient-based methods. Casgrain and Kratsios [02T] study the charac- terization of the regret-optimal algorithm given an objective function, using a value function- approach motivated by optimal control. In contrast, we aim to learn the optimal algorithm from a sequence of optimization problems, with potentially different objectives and characteristics.
Learning to optimize. Learning to Optimize (L20) is related framework with focus pirical methods. The goal is to learn an optimizer, usually parameterized by a deep neural network, automatically on set of training problems that can also generalize to unseen problem instances. Andrychowicz et al. (016)) propose learning updates in a coordinate- wise fashion using an LSTM ar- chitecture. Wichrowska al. 2017 later suggest several modifications improve the generalization capabilities of learned optimizers. More recently, Metz et al. 2022 proposes a learned optimizer trained wide variety of tasks, using evolutionary strategies for estimating gradient updates the meta-optimizer.
Meta Meta-learning, Meta-learning Thrun and Pratt 1998] Finn et al. 2017 aims to learn algorithms or model parameters that can adapt rapidly to new tasks. Regret guarantees over model parameters for online meta-learning
developed in Finn et al. [2119] J. and guarantees for adaptive gradient-basse
meta-learning were given in Balcan et al. 2219). The latter work provides guarantees for meta- learning optimization algorithms, but the performance metric in this context is upper bound on the actual performance. In contrast, meta-regret measures the performance gap directly and minimizing it is nonconvex problem, necessitating the use of techniques from online nonstochastic control theory.
1.4 Structure of the paper
we introduce the new control formulation of meta-optimization. and elaborate on the assumptions needed to apply the nonstochastic control framework. In Section g we state the algorithm and main results, well as the benchmark algorithm class. Illustrative experimental
In Section 2

---

results of our oetta-optiizztiinn methods are given in Section 4 In Appendix A and B we give more background on the historical use of control theory optimization. We describe the recent framework of online nonstochastic control in Appendix C and why it is important for meta-optimization. Generalizations of our dynamical system formulation to capture smooth convex meta-optimization is given in section D More expressive optimizers are given in Appendic El The extension to the stochastic and deterministic settings is given in Finally, we include more experiments, their descriptions and settings in Appendix
2 Online control formulation of meta-optimization
In this section, we explain our control formulation of the meta-optimization problem, representing first step to developing an efficient control-based method. Different from historical perspectives, which we outline in Appendices A and B our formulation gives rise to optimal control problem rather than a stability analysis.
In its simplest form, an optimal control problem is a minimization problem over the controls:
min Mi MT
Σ ce(ze, uz)
s.t. 2++1
Azt + Bu, + Wi-
The states are denoted as 2g, and for a linear dynamical system they evolve according to the dynamics determined by A and B. The control signals and disturbances are denoted as u, and w,, respectively, The control objective is the sum of control costs ct, which are functions of the states and controls. This optimization problem has explicit solutions under certain conditions, we know the cost functions a-priori; however, since mntaaoopiiizztioon is inherently online, we turn to the more recent regret-based online control setting.
In online control, the convex cost functions can appear in an adversarial fashion, and the controller can choose the controls iteratively as the cost functions are revealed. The goal in online control is to minimize policy regret:
Ce(EE, u.) min aelle
Σ
cx m
where Il denotes the comparator policy class, =;, uu denote the state and controls under the policy π, respectively. The policy regret is the excess total cost of the control algorithm, compared to that of the best controller in II. in hindsight. In the following discussion, specify how meta-optimization can be formulated as an online control problem.
For simplicity, consider the online convex optimization setting where all objective functions fts Rd + R are convex quadratic. Denote the location- indepenndnnt Hessian as V f(,( = H e Idddd, This setting can be generalized to convex smooth functions, as we detail in Appendix D We assume that the functions have bounded Hessian, and the gradients satisfy:
Assumption 1. Vi [N], E (7), Rdd, [+]]] < 2, +
The dynamical system. The state of the dynamical system at time (t. i) is given by the vector below consisting of the current optimization iterate, the previous iterate, and the previous gradient,
Ft,é
21,i
It It-15
V
For extension of the control formulation to include more iterates and gradients, see Appendix
E
Let > 0 be a regularization parameter, and 17 > 0 be the base learning rate, consider the system:
It+1.5
(1 (1
8)1
-nl
Dt,5
[
0
Ft,i
=
1 0
0
X
1.1
0 0 X U4
0
H4,
H
V
15-1,
1,))
[[
(3)
5

---

which is a valid representations of the optimization process given the relation
Vf,i( = Vf(.(3)11..) + H4,(T 121
The disturbance in the system evolution includes (2 component, which is not stochastic in nature. Consequently, classical control approaches such as H2 optimal control are not applicable, and we adopt the online nonstochastic control framework | This formulation also enables to capture the state reset when a new episode begins by using adversarial disturbances.
Without the control signal Ur the system describes the partially time-delayed gradient descent update with lg regularization: 2,41, = (1- ,) - vf Several results show that under mild conditions, the regret using delayed gradients are constant factors away from online gradient descent using using fresh gradients [Quanrud and Khashabi 2015, Langford et al. 2009]. The parameter 8 is user-specified to ensure stability, and can be arbitrarily small.
The control signal Ut contributes only to the update of Ft.i, and does not affect the rest of the state. Observe that we can simulate any optimizer's update by using the control signal, and therefore we can learn the best optimizer in hindsight by optimizing over the "e,, ss.
In meta mneaa-optimizaton. the dynamical system evolves according to (3) during an episode. However, each episode starts with the optimization iterate at an arbitrary initialization 3 and we need to reset the system before a new episode begins. To transition the system state to the new initialization, consider the following reset disturbance,
11,4+1 ((1 - --)00 - I1,41 - TT (fr,(FT-1.) (TT,(
ur,s))
WT.1
(4)
where u is the top d entries of the control signal uT.;- Under this reset disturbance, the initial state of an episode is 21,i = [oT, =T, ]_ which is consistent with the meta-optimization protocol. Finally, we assume that the initial point in each episode has bounded norm.
Assumption 2. For all i, I1,; satisfies || < R.
Online control formulation. Consider the online control problem 2 according to (3) and the control costs are the optimization objectives,
where the system evolves
min selle
f..()T,))
(5)
Note that the cost functions are functions of the states: (2, Ue,)) (1,,) (z ) where S is a matrix that selects the first d entries of 2t,,. In addition, observe that even though the cost functions do not explicitly depend
the controls ur they still affect the states through the control policy. This online control problem directly corresponds to meta-regret minimization, where the benchmark algorithm class II consists of optimizers whose updates match the dynamics of system G under controllers in IIc.
Stability. In nonstochastic control, stable system access to stabilizing controller is necessary to achieve regret that is polynomial in the state dimension Chen and Hazan 2021]. The notion of stability in this context is stronger than the conventional notion, and for linear time-varying (LTV) dynamical systems, is referred to as sequential stability. We assume our system satisfies this condition.
Definition 2.1 (Sequentially stable). An LTV system whose dynamics at time t is 2e+1 As Bru, +w is (R, 7) sequentially stable for all intervals = [r, S [T], IIITE_, A.ll S x12(11))111 Assumption 3. For settings where the functions ft, are changing, we assume that the resulting dynamical system is sequentially stable with 2
'Noicee that the regret bounds we prove are under the same sequence of disturbances, and apply to the gradients along the taken trajectory. This is similar to the nature of adaptive gradient methods: the best regularization in hindsight depends on the observed gradients, rather than the ones that would appear had we used a different algorithm.

---

The above assumption is standard in the literature of nonstochastic control for time-varying varying systems Gradu al. 2020b Minasyan et al. [02T]. the dynamical system is linear inverintaiannt (LTI), then Assumption S is satisfied if the system is strongly stable, whose definition is given below.
Definition 2.2 (Strong stability). system 24+1 = A2t + Bu, + We is (N.
?) strongly stable if there exist matrices P. Q, such that A PQP-1 and ||Q]| = 1 % || P 11 K.
In the deterministic meta-optimization setting, we have an LTI system. We show the appendix that with 77 scaling inversely as the smoothness of the function, and arbitrarily small, the LTI system is strongly stable for some (). The condition on r) is natural, since gradient descent with learning rate larger then B diverges.
3 Algorithm and main theorem statements
In this section, we give an efficient algorithm that minimizes meta-regret and state accompanying guarantees. Our main algorithm for quadratic meta-optimization is given in Algorithm 2 This algorithm views meta-optimization as a single-trajectory control problem, and uses the Gradient Perturbation Controller (GPC) method adapted from Agarwal et al. 2019]. The GPC method considers a specific class of controllers, namely fisturbance-feedback controllers, that are linear in the past disturbances, as defined below.
Definition 3.1 (Disturbance-feeell
controller). A disturbance-feedbat controller (DFC), π (M) is parameterized by sequence of L matrices {M') R==, where M denotes the 1-th matrix, instead of matrix power. It outputs the control signal u Σ i= M'
The GPC method uses the class DFC controllers, and makes gradient updates on the parameters of interest, M, to compete with the best DFC in hindsight.
Similar to the GPC method, at each time step, Algorithm outputs the control signal generated by T (Me,)), and receives an objective function. Then, the disturbances are computed according to the dynamical system formulation ( and a cost function for updating M is constructed on Line Finally, gradient update is executed on M.
The surrogate cost on Line has the following expression:
(6) where the surrogate state Vt,: is the state reached at time (t, i), if æt-Li = 0 and we execute the gt.
M,) (B. Mc-1,)))
sequence of policies MI-L.s...... .M---.. Note that the function gt.; function of only M, instead of a sequence of time-varying controls. As a result, when we take a gradient of gt.; (M), the gradient captures the effects of changing M over multiple time steps.
is
For smooth convex optimization, we cannot directly observe the dynamics Ar,5- There are two consequences for algorithm: we cannot access the full gradient with respect to M, and cannot compute it, directly. However, a bandit variant of Algorithm algorithm approximates at.a (M..... .M), and estimates the gradient of M with zeroth-order methods. The algorithm is given in Appendix D
2 overcomes both difficulties, as the
3.1 Guarantees for quadratic and smooth meta-optimization
We first state the regret guarantees of our algorithms, and describe the benchmark algorithm class in more detail in the next subsection. All proofs are in the full version at at/xttps:/arxxvvorg abs 22011231..2 07902
Theorem 3.2 (Quadratic). Under Assumptions e ((VNT)-1, and T. Ollog NT) satisfies
Algorithm
with n S 1,8 E (0, H T
MetaRegret Σ
min AeT
f((())) < & Ö(VNT),
where & contains polynomial factors in - N, R, b, and Ô contains these polynomial factors as well as logarithmic factors in T, N.
7

---

Algorithm 2 Gradient perturbation controller for meta-optimization
1: Input: N, 21,1, 7) 6. Mg. starting points { k- R,
2: Set: M = {M = {M
M² || I (1- (1--))),, 7)), and initialize any M1,1 E M.
3: for = 1, N do
4: If > set 21, 21-1--1, M1 = MI+1,611
5: fort=
do
6: Choose ue,i Σi= Mf, 1,-1, and observe 1t
7:
Receive fr,i, compute Vzt, (f.:((1-11)) If T. compute wr,, according to
8:
Suffer control cost (z, = ft,((
9:
Construct ideal cost (M.((M) = Dt. (M, ...,, M) according
10:
Perform gradient update on the controller parameters, where II denotes projection :
M4+1, [M, ny (M,.).
end for
12: end for
follows from lower bounds in online convex optimization Hazan et al. [016 that the dependence
of meta-regret N, T are optimal in Theorem 3 The next theorem holds for meta-optimizationn over convex smooth objectives, and the additional assumptions are given in Appendix [D] A Algorithm D.2 and the proof of Theorem 3.3 are based on nonstochastic control techniques in the bandit setting Gradu et al. 2020a
Theorem 3.3 (Smooth). Under Assumptions
2
3
Algorithm D.2 with 1, L= = O(log NT),
there exists setting of 8M, ( that satisfies
N
T
N
T
E MMetaRegrer]
= E
min Aell
Σ
Salatt Ö((NT)))1))
where Ô contains polynomial factors in 1 R, and logarithmic factors in T.N.
Remark 3.4. Stronger performance metrics that are more suitable for changing environments, such as adaptive regret and dynamic regret, were explored in the context of control of time varying dynamical systems, see [Gradu et al.] 20206 Minasyan el al. 2027J. These latter results can potentially be adapted to give stronger performance guarantees in cetta-pptiizzatin.
Analysis overview and technical novelty. The regret of Algorithm 2 is the excess total cost of controller compared to that of the best fixed DFC in hindsight. Since the system is strongly stable, the control cost at (t, i) depends minimally on the controls executed before L time steps, e.g. MI-L,; M .... Therefore, we can focus surrogate cost that is function of only the past control signals, where is logarithmic the horizon NT. Bounding the regret then reduces to obtaining low regret such surrogate costs, which was studied in the online learning with memory (OCOwM) framework Anava et al. (015)..
Crucially, this analysis relies on universal upper bounds on the states and disturbances, which is the main technical challenge of this work. Indeed, this assumption does not hold our setting, since the disturbances include (z,,,.) Under the smoothness assumption, ||Wt, can grow proportionally with |,,]-, Furthermore, the reset disturbance can be on the same scale as the states themselves.
We overcome this challenge by showing that due to system stability, the effect of the reset disturbance attenuates exponentially. In each episode, after the initial large reset disturbance, the state and disturbance have an upper bound that decreases with time and eventually converges to a constant value. Moreover, if we scale the objective functions properly, we can bound the contribution from Wy.; to the size of the state because of smoothness. make this intuition formal, we use several inductive arguments address the interdependence between the states and disturbances.

---

3.2 The benchmark algorithm class
We introduce the benchmark algorithm class we compete against, which consist of optimizers that correspond to class of DFCs. Informally, our guarantee is competitive with optimizers that are linear functions of past gradients.
The comparator policy class we consider for control is DrFc. the set of all disturbance-feedlaac policies defined by M such that M E M defined in Algorithm The GPC method obtains sublinear regret against DFC under a fixed sequence of disturbances, cost functions, and dynamics. However, if these sequences are fixed in meta-optimization, the gradient component the state is no longer the true gradient; instead, they are gheudo-gradieed Let zt,s denote the optimization iterate at time in epoch under controller T (M) E DD Define the pseudo-gradient at time (1, 8) as
A (+) = Vf (x. + (fL;(Z1-1,,),
where 1,- is the optimization iterate of our algorithm. Then the states under π (M) are
11
M 2,, Li (f,((11.))
21,
L1.i
2,
M 2,,
for t 2 3.
Vi M
Observe that each policy in DrF corresponds to an optimization algorithm. Writing out the control signals, the benchmark algorithm class consists of optimizaers with updates:
M 1-11 1, = (1 - 5) -
M w1-11-
This benchmark algorithm class has more straightforward interpretation for deterministic meta- optimization. can capture common algorithms on time-delayed descent, momentum, and preconditioned methods. For details the range of hyperparameters it contains, see Appendix G for concrete example of learning the learning rate, see Appendix H
including gradient
Experiments
We evaluate the empirical performance of our meta-optimization algorithm on a suite of tasks, including regression and classification. For an illustrative example, we consider regression with the objective A1 bll?. We first generate A and b element- wise using the standard Gaussian distribution. To simulate the stochastic meta-optimization setting, we have N episodes and time steps, and the optimization iterate is re-initialized the same point at the beginning of each episode. The initial value is randomly sampled. For each / E (T). and E [N], we add entry-wise standard Gaussian noise to b. We set d 100, T 500, N 10, and compare with gradient descent, (MP)
momentum, Marchenko- Paattuur and nesterov accelerated gradient. The Marchenko-Passe algorithm is optimal in the average-case sense for regression tasks whose design matrix has entries sampled from an i.i.d Gaussian distribution, and therefore should perform well in our setting without noise Pedregosa and Scieur 2020). We tune the learning rate and momentum hyperparameters for all algorithms, and the sweep details are in Appendix J For meta- meta-optimization, we use L = 3, 5 = and base learning rate of 0.001. We plot the moving average of the objective values in Figure with a window size of 50.
The plot shows that initially, meta-optimization has similar performance to other algorithms. However, with an increasing number of episodes, the algorithm gradually learns and outperforms baselines both the beginning and, eventually, towards the end of each episode. This illustrative experiment shows that for this particular problem, oottioopii can improve and learn updates that minimize the objectives quickly.
For proof-of- -onnccept nonconvex task, we consider MNIST classification with neural network. The network has 3 layers and is fully connected, with layer sizes [784, 512, 10]. We run for 5 episodes with 20 epochs in each episode. Since this problem is high-dimensional, we choose to learn scalar weights of past gradients. We take I = 20, and the network is trained using stochastic gradients from batches of size 256. The hyperparameters of the baselines are tuned, and the sweep details are in Appendix[] J We also include Adam in our baseline, since is popular optimizer.

---

Stochastic Meta vetamootimication
Meta
360
Nestery Momertum
340
big
4003
Imm
Figure 1: Comparison plot for the performance of meta-optimization and other baselines.
Ageethes
$6Q,10
008
Noslow
006
Meta
0.4
2500
3000
7500
33030
12500
25003
13500
20000
Figure 2: Comparison plot for the training performance of meta-optimization and other baselines with suboptimal base learning rate.
In this experiment, the base learning rate for the meta optimizer is set to 0.5 instead of the optimal learning for SGD, which is 1.0. We show the training curves of SGD with learning rates of both 1.0 and 0.5 for comparison. Examining the plot, it is clear that the meta optimizer outperforms SGD with learning rate 0.5 by wide margin, and continues to converge the performance of momentum over episodes. We include more experiments in Appendix
5 Conclusion.
This manuscript proposes framework for optimization whose goal is learn the best optimization algorithm from experience, and gives an algorithmic methodology using feedback control for this meta-optimization problem. In contrast well-studied connections between optimization and Lya- punov stability, our approach builds upon new techniques from the regret-based online nonstochastic control framework. We derive new efficient algorithms for optimiiiiin using recently proposed control methods, and prove regret bounds for them.
An interesting direction for future investigation is extending the work nonstochastic control of time varying and nonlinear dynamical systems to our setting meta-optimization. In particular, is inter- esting to explore the implications of low adaptive and dynamic regret in meta-optimization. Another area of investigation is the connection between meta-optimization using control, and adaptive methods: do the solutions proposed by the control approach have connections to adaptive regularization-bant algorithms? Many intriguing problems arise in this new intersection of optimization and nonstochastic control.
Acknowledgments and Disclosure of Funding
Flad Hazan acknowledges funding from the ONR award N0001423121566 the NSF award 21 2134040,
and Open Philanthropy.
10

---

References
Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances. In International Conference Machine Learning, pages 11 111-119, 2019.
Oren Anava, Elad Hazan, and Shie Mannor. Online learning for adversaries with memory: price of past mistakes. Advances in Neural Information Processing Systems, 28, 2015.
Marcin Andrychowicz, Misha Denil, Sergio Gómez Colmenarejo, Matthew W. Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando Freitas. Learning to learn by gradient descent by gradient descent. In Proceedings of the 30th International Conference on Neural Information Processing Systems. NIPS' 16, page 3988-3996, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN
Igor Babuschkin, Kate Baumli, Alison Bell, Surya Bhupatiraju, Jake Bruce, Peter Buchlovsky, David Budden, Trevor Cai, Aidan Clark, Ivo Danihelka, Antoine Dedieu, Claudio Fantacci, Jonathan Godwin, Chris Jones, Ross Hemsley, Tom Hennigan, Matteo Hessel, Shaobo Hou, Steven Kapturowski, Thomas Keck, Iurii Kemaev, Michael King, Markus Kunesch, Lena Martens, Hamza Merzic, Vladimir Mikulik, Tamara Norman, George Papamakarios, John Quan, Roman Ring, Francisco Ruiz, Alvaro Sanchez, Rosalia Schneider, Eren Sezener, Stephen Spencer, Srivatsan Srinivasan, Wojciech Stokowiee, Luyu Wang. Guangyao Zhou, and Fabio Viola. The DeepMind JAX Ecosystem, 2020. URL htto: /ttpt//////thb/../// com deepmind
Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for gradient-based meta-learning. In International Conference on Machine Learning, pages 424-433. PMLR, 2019.
Atilim Gunes Baydin, Robert Cornish, David Martinez. Rubio, Mark Schmidt, and Frank Wood. Online learning rate adaptation with hypergradient descent. arXiv preprint arXiv:1703.04782 2017.
Yoshua Bengio. Practical recommendations for gradient-based training of deep architectures. In Neural networks: Tricks of the trade, pages 437-478. Springer, 2012.
James Bradbury. Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL
http:// httt:://github. com goog le/ jax
Philippe Casgrain and Anastasis Kratsios.
Optimizing optimizers: Regret-optimal gradient descent algorithms. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 883-926. PMLR, 15-19 Aug 2021.
Kartik Chandra, Erik Meijer, Samantha Andow, Emilio Arroyo-Fang Irene Dea, Johann George, Melissa Grueter, Basil Hosmer, Steffi Stumpos. Alanna Tempest, et al. Gradient descent: The ultimate optimizer. arXiv preprint 1909::199991377/ 2019.
Xinyi Chen and Elad Hazan. Black-box control for linear dynamical systems. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 1114-1143, PMLR, 15-19 Aug 2021. URL
mlr wrw.sprssssse.. wtt..ppeee/////////ttt2//
Alon Cohen, Avinatan Hasidim, Tomer Koren, Nevena Lazie, Yishay Mansour, and Kunal Talwar. Online linear quadratic control. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 1029-1033 PMLR, 10-15 Jul 2018. URL http::ttppp:sceeeee
m1 r. wt..prss/vvet cohen Bb. html
Alon Cohen, Tomer Koren, and Yishay Mansour. Learning qinear-quadratic regulators efficiently with only VT regret. In International Conference on Machine Learning, pages 1300-1309, 2019.
Carles Doningo-Enrich, Fabian Pedregosa, and Damien Scieur. Average-case acceleration for bilinear games and normal matrices. International Conference on Learning Representations, 2021. URI. https: wpw.review nnt/ Howmmmidd-ossooyyaaa

---

Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agmostic meta- meta-learning for fast adaptation of deep networks. In International conference on machine learning. pages 1126-1135. PMLR, 2017.
Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta meta-learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1920-1930. PMLR, 09-15 Jun 2019. URL. ftttps://proceede ngs. ml press/ v97 Fi Finnnnne 1tt.mmm.....mmll.
Paula Gradu, John Hallman, and Elad Hazan. Non-stochastic control with bandit feedhack. Advances in Neural Information Processing Systems, 33:10764-10774, 2020a.
Paula Gradu, Elad Hazan, and Edgar Minasyan. Adaptive regret for control of time-varying dynamics, 2020b. URL
wttp://g//ggooooooooooo 04393
Elad Hazan and Karan Singh. Introduction to online nonstochastic control. arXiv preprint arXiv:2211.09617 2022.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimiza- tion, 2(3-4):157-3255 2016.
Rudolph Emil Kalman. A new approach to linear filtering and prediction problems. Journal of Basic Engineering, 82.1:35-45, 1960.
John Langford, Alexander Smola, and Martin Zinkevich. Slow learners are fast, 2009. URL
https: http///axivvv//a
00.1s//991..0 0491
Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1):57-95, 2016.
doi: 10. 10.1137715 WtRLhttps://dat htttbe///ooll.orr//1.1111/////// 1tt..//orr0..1113355550000555550 009597
Aleksandr Mikhailovich Lyapunov. The general problem of the stability of motion. International journal of control, 55(3):531-534, 1992.
Luke Metz, James Harrison, C. Daniel Freeman, Amil Merchant, Lucas Beyer, James Bradbury, Naman Agrawal, Ben Poole, Igor Mordatch, Adam Roberts, and Jaseha Sohl-Dickstein. Velo: Training versatile learned optimizers by scaling up, 2022.
2211.09760
Edgar Minasyan, Paula Gradu, Max Simchowitz, and Elad Hazan. Online control of unknown time-varying dynamical systems. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 15934-15945 Curran Associates, Inc., 2021.
Michael Muchlebach and Michael Jordan. A dynamical systems perspective on nesterov acceleration. In International Conference on Machine Learning, pages 4656 4662. PMLR, 2019.
Courtney Paquette, Kiwon Lee, Fabian Pedregosa, and Elliot Paquette. Sgd in the large: Average-case analysis. asymptotics, and stepsize criticality. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 3548 3626. PMLR, 15-19 Aug 2021.
Fabian Pedregosa and Damien Scieur. Acceleration through spectral density estimation. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Leurning. volume 119 of Proceedings of Machine Learning Research, pages 7553-7562. PMIR, 13-18 Jul 2020.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computa- tional mathematics and mathematical physics, 4(5):1-17, 1964.
Philip D. Powell. Calculating determinants of block matrices, 2011. URL Sittps//aaxxiv.o/
abs / /1112.111111 4379
12

---

Kent Quanrud and Daniel Khashabi. Online learning with adversarial delays. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and Garnett, editors, Advances Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
R Tyrell Rockafellar. Linear-quadratic programming and optimal control. SIAM Journal on Control and Optimization, 25(3):781-814, 1987.
Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control. In Conference Learning Theory, pages 3320-3436 PMLR, 2020.
Jean-Jacques Slotine, Weiping Li, al. Applied nonlinear control, volume 199. Prentice hall Englewood Cliffs, NJ, 1991.
Weijie Su, Stephen Boyd, and Emmanuel Candes. A differential equation for modeling nesterov's accelerated gradient method: theory and insights. Advances in neural information processing systems, 27, 2014.
Russ Tedrake. Underactuated Roboties: Algorithuss for Walking, Running, Swimming, Flying, and Manipulation (Course Notes for MIT 6.832). 2020.
Sebastian Thrun and Lorien Pratt, editors. Learning to Learn. Kluwer Academic Publishers, USA, 1998. ISBN 0792380479.
Jun-Kun Wang. Chi-Heng Lin, and Jacob D Abernethy, modular analysis of provable acceleration via polyak's s momentum: Training wide relu network and a deep linear network. In International Conference on Machine Learning, pages 10816-1082) PMLR, 2021a.
Xiang Wang, Shuai Yuan, Chenwei Wu, and Rong Ge. Guarantees for tuning the step size using Souming-to-learn approach. In International Conference on Machine Learning, pages 10981-10990. PMLR, 2021b.
Olga Wichrowska, Niru Maheswaranathan, Matthew W. Hoffman, Sergio Gómez Colmenarejo. Misha Denil, Nando de Freitas, and Jascha Sohl-Dickstein. Learned optimizers that scale and generalize. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3751-3760. PMLR, 06-11 Aug 2017.
Ashia Wilson. Lyapumov arguments in optimization. University of California, Berkeley, 2018.
13


Reviews:
[{"review_id": "3irqiQv3P2", "reviewer": "Reviewer_yXWX", "summary": "The paper considers a new framework, meta-optimization. To solve this problem, the authors propose an online control formulation with linear time-varying dynamics. Moreover, a novel algorithm is proposed to solve meta-optimization and shown to enjoy sublinear regret under both the quadratic loss and convex smooth losses. As an application, one can formulate the hyperparameters, such as learning rate, as a meta-optimization problem. Finally, the authors provided experiments to show the algorithm's superior performance compared to existing hyperparameter tuning benchmarks. ", "questions": "I have some minor questions:\n1. The formulation proposed in Lines 57-58 seems not to be used in the analysis. Equation (5) is a more concrete formulation for meta-optimization. Could you explain why to need this generic formulation and how it is related to other formulations?\n2. The online control formulation (1) - (3) involves a control variable $u_{t, i}$ while it is missing in (5). What is the meaning of this control signal for meta-optimization and, more concretely, in learning gradient descent step size?\n3. What is the intuition behind using ideal cost $g_{t, i}$ in Algorithm 2?", "limitations": "The limitations and future work have been addressed in the conclusion section. ", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The authors consider a new framework, meta-optimization, to choose the optimal hyperparameters. \n2. The authors point out that meta-optimization with gradient descent methods can be viewed as an online control formulation with linear dynamics.\n3. A new algorithm is proposed to solve the meta-optimization problems inspired by the online nonstochastic control formulation. New techniques are used to show the sublinear regret for meta-optimization with quadratic and convex smooth losses.\n4. Comprehensive experiments are conducted and comparisons to benchmarks are provided. \n5. The paper is well-organized and well-written. ", "weaknesses": "1. Several online optimization problems are proposed, while not all of them are used to reach the final goal. The authors may reorganize the presentation and clarify the relation between the formulations. \n2. It is preferred if the authors can mention the techniques used in the main text following the main theorems. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive evaluation of our work and the helpful suggestions. To address the weaknesses, we are very happy to clarify the online optimization formulations in the revision, and include more techniques that are used in proving the main theorems. \n\nFor the questions:\n1. This formulation uses short-hand notation on the episodic loss, but it is not necessary. It is the same as (5), which expands the episodic loss. We can remove the redundant one for the final version.\n2. The control variable in (5) is implicit in $x_{t, i}^\\pi$, where $\\pi$ denotes the control policy. $x_{t, i}^\\pi$ is the state reached under the policy $\\pi$ at time $(t, i)$, so while the control cost $f$ doesn’t take the control signal $u_{t, i}$ into account, the state is still affected by the control policy. In meta-optimization, the control signal can be used to simulate the update of any optimization algorithm; therefore, through learning the best controls, we can compete with the best optimizer. The control signal, including learning the gradient descent step size, is a linear function of past disturbances, which largely depends on the past gradients.\n3. We use the ideal cost because we need a loss function that depends only on $M$ to update it. The original control cost is a function of $x_{t, i}$, which depends on $M_{t, i}, M_{t-1, i}, \\cdots$. On the other hand, the ideal cost is the cost that we would have incurred, if we started from the zero state and executed $M_{t, i}$ for $L$ time steps. It is a function of only $M_{t, i}$. There are two reasons why using the ideal cost works for non-stochastic control, which we elaborate in the appendix. In summary, the reasons are:\n- The system is stable, and therefore the control cost depends minimally on the controllers executed before $L$ time steps, e.g. $M_{t-L, i}, M_{t-L-1, i}, \\ldots$. \n- We update the $M_{t, i}$’s with a memory-based OGD algorithm developed under the online convex optimization with memory framework, which accounts for the fact that the original control cost can depend on $L$ inputs, and still gives us the desired guarantee.\n\n"}, {"review_id": "eIBtPXGZ6L", "reviewer": "Reviewer_PoEe", "summary": "This paper proposes an online control method to meta optimization problem. The authors formulate the problem into a robust control problem and leverages non-stochastic control framework to achieve convex relaxation. The regret guarantees are derived theoretically and experiments show its superiority compared with the best optimizers in hindsight.", "questions": "In line 7 of Algorithm 2, how is the gradient information calculated. If it is calculated through approximation (e.g., finite-difference), how will the approximation error affect the final outcomes?\n\nIs the meta regret of the proposed method always positive? Because intuitively, the best optimizer in hindsight should always perform better. If yes, why the proposed method can achieve lowest loss in all experiments compared with all other optimizers?", "limitations": "The limitations of the proposed method is not explicitly discussed in conclusion, although future directions are pointed out.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The main text is very concise in presenting the main technical discovery of the paper, as well as necessary background discussion and experiment results. The appendix provides very comprehensive introduction of technical background, proof of theorems and more interesting experiment results. This paper is overall well written and solid in theory.", "weaknesses": "I personally think the experiment presented in the main paper can be replaced by a more complex one. For example, could you consider experiments with neural network training using Adams, which will be more interesting to modern AI field. Or any other complex experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review our work and the valuable feedback. Given your suggestion, we have added a proof-of-concept experiment for neural network classification on the MNIST dataset, with Adam as one of the baselines. Additional comments and details on the experiment are in the top-level response. \n\nTo address your questions:\n1. In Line 7 of Algorithm 2, we assume access to the exact gradients of the function. If we use finite-difference, under Lipschitz loss functions, the approximation error of the gradients will be added linearly to the regret; in other words, the sum of all biases will be added to the final regret. If the gradients are stochastic with zero mean noise, the expected regret will remain the same. \n\n2. The meta-regret of a method can be negative if the method does better than the best optimizer in the benchmark algorithm class $\\Pi$. The proposed method can compete with a class of optimizers that include preconditioned methods (see appendix G and H), and Newton’s method converges in one step for quadratic minimization problems. Our baselines in the experiments are mostly first-order, since they are the most popular optimization algorithms. \n\nGiven the positive evaluation of novelty and contribution in this review, and the additional nonconvex optimization experiment, we hope the reviewer is open to raising their score."}, {"review_id": "vPvvrGUcfq", "reviewer": "Reviewer_fcBo", "summary": "This paper proposes a framework for optimization whose goal is to learn the best optimization algorithm from experience, and gives an algorithmic methodology using feedback control for this meta-optimization problem. The authors derive new efficient algorithms for meta-optimization using recently proposed control methods, and prove sublinear meta-regret bounds for quadratic and convex smooth losses. The approach leverages convex relaxation techniques in the recently-proposed nonstochastic control framework to overcome the challenge of nonconvexity. Consequently, it enables us to learn a method that attains convergence comparable to that of the best optimization method in hindsight from a class of methods.\n", "questions": "This is a very solid theory paper. However, in the main paper, the experiment part is limited. Can we move Logistic regression for MNIST classification experiment from Appendix and add to main paper?  In Figure 1, for y-axis, is it the moving average of objective values on training data or validation data?\n", "limitations": "There is no code provided to reproduce the results.\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper introduces a novel approach based on control theory for the task of meta-optimization – online learning of the best optimization algorithm. It provides a novel control formulation for meta-optimization based on the recently proposed framework of online nonstochastic control. Consequently, a new metric for meta optimization called meta-regret is proposed, which measures the total cost compared to the cost of the best algorithm in hindsight in meta-optimization. FurthermoreMoreover, this is a theoretical paper of high technical quality. It derives efficient algorithms for meta-optimization based on recently proposed Gradient Perturbation Controller (GPC), a new type of online feedback-loop controller. Furthermore, this paper provides the analysis and proof of the tight sublinear regret bounds for quadratic and convex smooth objective functions.\n", "weaknesses": "This paper is well organized and clearly written in general. However, in algorithm 2 (Line 9), Eq. (7) is missing in the main paper, although we may find this Eq. in Appendix. This is mainly a theory paper, in section 4, it provides an proof of concept on experiments with quadratic and convex smooth losses. We are curious to investigate the empirical impact of meta-optimization on board applications. Therefore, it might strengthen the impact if the authors could provide the experiment on non-convex loss, for example, a classification task using simple neural network.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review our work and their valuable feedback. We are happy to address the weaknesses:\n1. We will provide explanations and intuitions for the ideal cost in the main paper, for clarity and completeness. \n2. We have an additional experiment on MNIST classification with a neural network. Comments and details on the experiment are in the top-level response. \n3. We definitely plan to open source our implementation in the coming weeks, as soon as we can. \n\nFor the questions:\n1. We can certainly move the logistic regression experiment to the main paper.\n2. In Figure 1, the objective values are on the training data, since we study optimization instead of generalization. \n\n\n\n"}, {"review_id": "lnyyrSCEn1", "reviewer": "Reviewer_MnL8", "summary": "This paper studied the problem of meta-optimization through the perspectives of online control. In this paper, the meta-optimization problem is thought as a sequence of episodic optimization problem and the performance is measured by the regret against the best static optimizer belonging to a convex class. By re-writing the gradient descent update rule into a LTV system with non-stochastic disturbance, the author presented a control-motivated meta-optimization algorithm can achieve nearly-optimal optimization performance in hindsight. The main theorem shows that the algorithm proposed by this paper can achieve sub-linear regret for both quadratic and convex, smooth costs.", "questions": "See my concerns above. I am open to raising my rating significantly if author can either prove me wrong or offer fixes to these issues.", "limitations": "This paper is mostly theoretical and addresses fundamental problems in optimization for ML. So, I do not envision any concerns over ethics.\n\nHowever, the authors absolutely should include source code for their experiments, especially since their proposed algorithm is quite involved.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "I think the approach taken by this paper is quite clever in that it re-write the extremely difficult, highly non-convex meta-optimization problem into a much more tractable online learning problem. The idea seems quite general and I encourage the authors to extend this work to meta-optimize more sophisticated algorithms beyond standard gradient descent (e.g. momentum or Adam).\n\nThe use of regret to benchmark the performance of meta-optimization also seems to be a good idea, as it balances the desire for fast convergence and quality for the final solutions.\n\nGiven this is a ML venue, this paper did a good job with introducing the relevant notations and terminologies from control.", "weaknesses": "While I think this paper has a lot of potential, I regrettably cannot given a strong rating because I feel the presentation is overall quite lacking.\n\n1. I do not agree with the author's claim that their setting of meta-optimization generalizes hyper-parameter optimization. While, the algorithm in this paper can yield comparable performance to the best hyper-parameters in hindsight, I struggle to find how a good set of hyper-parameters can be extracted this algorithm.\n\n2. This paper seems a bit carried away with the control perspective and fails to give concrete examples how the results can be applied to practical learning problems. Although an example is given in Appendix I, it is rather simplistic. And the lack of source code makes it hard for the readers to understand how the algorithms are implemented.\n\n3. Some of the notations are not very well-specified. a) the disturbance $w_{t, i}$ is not explicitly defined, is it $\\nabla f_{t, i}(x_{t-1} i)$ as given in eq. (3)? b) in Theorem 2, what is the function class $\\Pi$, is it related to $\\Pi_{DFC}$?\n\n4. Regarding the equation between lines 196 and 197, isn't it a second order approximation of gradient descent? This simplifying assumption should be discussed more thoroughly.\n\n5. Algorithm 2 should be more self-contained, i.e., eq. (7) should be in the body. Also I would love to see more description on this algorithm.\n\n6. Perhaps my greatest complaint. The experiments are very simple and does not reflect any realistic scenarios where meta-optimization are helpful. Linear regression and MNIST are both too small that vanilla SGD can usually get very good performance already. Also, I very much don't like the decision to move almost all of the experimental details into the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review our work and the valuable feedback. We first address the point of simple experiments, and then address other comments one by one below.\n\n**please also see pdf for all reviewers, as it contains experiments**\n\nWe would like to emphasize that this is mainly a theoretical paper, and in our opinion this work has sufficient novelty to stand alone as a conceptual and theoretical contribution. To elaborate on the difficulty of getting this result, and the techniques from different subfields that we needed to incorporate to circumvent known NP-hardness results:  we change the formulation of the problem and incorporate convex relaxation (point 1 below), we give a new dynamical system formulation of optimization (which is different from all previous formulations), and we use new techniques from online control to solve this dynamical systems formulation (which have not been used in optimization before). Notice our method can also compete with gradient descent with momentum, and preconditioned methods, which is a strength you wanted to see in future work (and is already accomplished in this paper). \n\nTo support the theory, we provide proof-of-concept experiments, rather than extensive evaluations as in applied papers. The existing experiments are consistent with the convex regime studied in the paper, and we include an additional experiment on neural networks in the general response. Even though SGD can solve these problems, it still requires hyperparameter tuning to achieve the best performance, and as shown experimentally, meta-optimization has improved performance over time. Extension to non-convex meta-optimization and developing practical algorithms suitable for ultra large-scale optimization is important future work. These experimental results also demonstrate that there is potential for this new approach to be applied to a broader set of problems, including nonconvex optimization with large-scale deep neural networks. \n \nWe respond to your other comments below:\n\n1. Directly optimizing over the hyperparameters is a non-convex problem in general, and non-convex problems are NP-hard in the worst case. We use an improper learning technique, meaning that we do not directly manipulate the hyperparameters but the optimization iterates themselves. This improper learning technique is the result of a convex relaxation, and this combination of techniques to tackle non-convex problems is commonly used in the theoretical machine learning community. A prominent example is the LASSO algorithm: it relaxes the sparsity constraint to an $\\ell_1$ constraint. This circumvents the NP-hard problem of recovering the sparse coefficients, and allows for equal expressive power in prediction/classification. (Note there is a large literature on statistical assumptions that allow for recovery of the sparse coefficients, we do not refer to these). Other examples include: online nonstochastic control (which we make use of), trace norm relaxation for matrix completion, and many more.       \n  \n    The notion of competing with the best-in-hindsight in terms of performance, a.k.a. regret minimization, is also a widely adopted paradigm. Notably, adaptive gradient methods (starting from AdaGrad) were developed in this context.\n\n    For hyperparameter optimization, our approach which makes use of convex relaxation and regret minimization, improves upon grid search of hyperparameters in terms of the iterates. In particular, if we can compete with the best optimizer in hindsight, the optimization iterates will converge to the optimum faster over many episodes, compared to grid search. \n\n    Lastly, the relationship between the best disturbance-response controller and the optimal state feedback controller, which directly encodes the hyperparameters, is an interesting research topic. Indeed, [1] shows that in the LQR setting under certain conditions, parameters of the disturbance-response controllers are good approximations of the optimal feedback controller. \n2. We describe the control approach in detail because it is the foundation for our algorithm. The example in Appendix I is simple to illustrate the theoretical approach. In appendix H, we give examples of optimization algorithms that we can compete against, which include essentially gradient descent with momentum, and preconditioning methods. We plan to open source our code in the coming weeks and make our method more widely available as soon as we can. \n3. Thank you for pointing them out, we will clarify in the revision. (a) Yes, $w_{t, i}$ is as defined in (3) during an episode, and as in (4) at the end of an episode. (b) The algorithm class $\\Pi$ and its relationship to $\\Pi_{DFC}$ is explained in section 3.2.\n4. This equation represents the relationship between the previous gradient and the current gradient. In the convex quadratic case, the $H_{t, i}$ matrix is the Hessian; in the convex smooth case, there always exists such a linear transformation and we consider a particular one, as stated in the appendix. The linear transformation is given by second-order information of the function at different points between the previous and current iterate. \n5. Thank you for the suggestion, we will include the ideal cost and more exposition on the algorithm in the main body. We have also commented on the intuition behind the ideal cost in the response to reviewer yXWX.\n\n[1] On the Relationship of Optimal State Feedback and Disturbance Response Controllers\n\nWe hope our response answers your questions and that you consider raising your score. \n"}]

Author rebuttal:
**please see attached pdf**

We thank all reviewers for their time and valuable feedback. One common suggestion is including more complex experiments, for example with neural networks. Since the main contribution of this paper is theoretical, the experiments are proofs-of-concept to show the potential of this theoretical framework. The existing experiments are in the convex regime, consistent with theory and empirically support our theoretical results. 
For the purpose of showing potential of future applications/theory to practical optimization settings, we give a proof-of-concept additional experiment in the non-convex regime, namely MNIST classification with a neural network in the uploaded PDF file.

As can be seen in the first experiment, given a good base learning rate ($\eta$ in the algorithm), meta-optimization improves over SGD, Adam, and momentum (with tuned hyperparameters). The performance gap also widens as there are more and more episodes. In the second experiment, we give meta-optimization a suboptimal base learning rate (0.5), and show that the meta optimizer not only outperforms SGD with lr=0.5, but also SGD with lr=1.0, and approaches the performance of momentum, the best baseline. Given these initial positive results, we believe that the meta-optimization framework holds much promise and this work lays a solid theoretical foundation for future research.

Experimental details: We consider the MNIST classification task with a neural network. The network has 3 layers and is fully connected, the layer sizes are: [784, 512, 10]. We run for 5 episodes with 20 epochs in each episode. Since this problem is high-dimensional, we choose to learn scalar weights of past gradients. We take L=20, the meta learning rate = 0.005, and we have found that the results are insensitive to the meta-learning rate choice. The network is trained using stochastic gradients from batches of size 256. The hyperparameters of the baselines are tuned, and the search space is the following:

SGD: learning rate = [1e-5 to 10] with increments of factor 10

Momentum: learning rate = [1e-5 to 10] with increments of factor 10, momentum = [0.9, 0.95, 0.99]

Nesterov momentum: learning rate = [1e-5 to 10] with increments of factor 10, momentum = [0.9, 0.95, 0.99]

Adam: learning rate = [1e-4, 1e-3, 1e-2], beta_1 = [0.9, 0.95, 0.99], beta_2 = [0.9, 0.95, 0.99]
For Adam, the learning rates 1e-4 and 1e-2 were already suboptimal, so we did not search beyond them. 


Meta-review: This paper casts meta-optimization (the task of learning the best optimization algorithm) in terms of control theory, and uses convex relaxation techniques to obtain regret guarantees, despite the non-convexity of the problem. 

The reviewers unanimously agree that the paper is well-written, and its contributions merit acceptance. I agree with them and think that this paper will spark fruitful discussions at the intersection of optimal control and meta-optimization. Consequently, I recommend this paper be accepted as a spotlight. 

Please incorporate the reviewer's comments in the final version of the paper. In particular, addressing the following concerns will help strengthen the current version of the paper:
- Add the non-convex MNIST experiments that were included as part of the rebuttal, and open-source code.
- Provide better intuition and exposition behind the ideal cost and resulting algorithm.
Decision: Accept (spotlight)