Learning to Optimize via Dual space Preconditioning
Authors: Sélim Chraibi
Adil Salim
Samuel Horváth
Filip Hanzely
Peter Richtárik
Venue:  (2020)
Keywords: Optimization
meta-learning

Abstract: Preconditioning an minimization algorithm improve its convergence and can lead to a minimizer in one iteration in some extreme cases. There is currently no analytical way for finding a suitable preconditioner. We present a general methodology for learning the preconditioner and show that it can lead to dramatic speed-ups over standard optimization techniques.
   

Under review as a conference paper at ICLR 2020
LEARNING TO OPTIMIZE VIA DUAL SPACE PRECONDITIONING
Anonymous authors Paper under double-blind review
ABSTRACT
Preconditioning minimization algorithm improve its convergence and can lead to a minimizer in one iteration in some extreme cases. There currently no analytical way for finding suitable preconditioner. We present general methodology for learning the preconditioner and show that it can lead to dramatic speed-ups spedd-ups over standard optimization techniques.
INTRODUCTION
Many problems arising in applied mathematics can formulated as the minimization of a convex function f IRd + (-o0, +oo|
min f(x). #ER
The resolution of optimization problem is usually tackled using an optimization algorithm that produces sequence of iterates converging to some minimizer (Nesterov (2018). The gradient descent algorithm is a standard optimization algorithm that converges linearly (i.e exponentially fast) if f is regular enough. Preconditioned methods (Nemirovsky & Yudin (983); Lu et al. (0166); Maddison et al. (2019) are powerful optimization algorithms that converges linearly under weaker assumptions that gradient descent. The performance of these methods relies heavily on the pre- conditioning the task of choosing the hyperparameter called the preconditioner. In the case of the Dual space Preconditioned Gradient Descent (DPGD) of Maddison et al. (2019), an optimal preconditioning can lead convergence in one iteration.
The preconditioner is function that has to be selected properly w.r.t. / to obtain the desired linear convergence. Although Maddison et al. (2019) gives some hints to precondition DPGD, there is currently no analytical way for finding suitable preconditioner.
In this paper, we propose learn the preconditioner of DPGD using neural network. We make the following contribution:
We propose supervised learning setting to learn the preconditioner of an optimization algorithm (DPGD, Maddison al. (2019)
We present a general methodology that allows effectively learn the preconditioner while avoiding issues related to this task
We implement this methodology in dimension and 50 and show that this can lead to dramatic speed-ups.
The remainder is organized as follows. The next section provides background knowledge on the DPGD algorithm. Then, in section we present our supervised learning setting. Finally, apply this methodology in section 4 Additional developments are provided in the appendix as well as postponed proofs.
BACKGROUND ON DUAL PRECONDITIONING
The main message of this section is that good preconditioner is preconditioner that is "close" to Vf*, where f is the Fenchel conjugate of f.

---

Under review as a conference paper at ICLR 2020
2.1 LEGENDRE FUNCTIONS
Before introducing DPGD algorithm, we need to define the class of functions f that we aim to minimize. These functions are called Legendre convex functions and are studied in (Rockafellar 1970 Section 26). We recall their definition and some of their properties. Given a function f R -00, 20], the domain of f is the set {ar R.
R f(x < oo). We denote (ff) the interior of the
domain of
Definition 1. The function f is Legendre if D(f) is not empty, and if
the function f is lower semicontinuous on RR, and is differentiable and strictly convex on D(f).
the gradient f is coercive on D(f): For every sequence (Ie)iEN & D() converges point on the boundary of the domain of |/ fx:)) + co.
Given Legendre function f, one can define its Fenchel conjugate f*(v) sup v) f(x). Proposition (Rockafellar (1700). The function f is Legendre and only if its Fenchel conjugate f is Legendre, in which Vf is one-to-one between D(f) and D(f*). Moreover, V is continuous in both directions, for every x E D(f), V (f V (y)) y.
and for every y E D(f*),
Proposition (Rockafellar (1700). If f is Legendre, then it either has minimizer or one unique global minimizer T. E D()). f admits a minimizer, then V f(x,)) 0, 0 E D(f*) and
T. (0).
2.2 DPGD ALGORITIM (MADDISON ET AL. (2019))
Consider convex Legendre function written
Rd (-x0, +00). To minimize f. the DPGD algorithm is x = x
Vp(0))
(I)
where y > and p Rd + (-00 +o0 are parameters. DPGD is well defined over the set of
Legendre convex functions f, see Maddison al. (2019). The map Vp is called non-linear preconditioner of f.. The preconditioning is the design Vp.
2.3 CONVERGENCE THEORY OF DPGD
In the sequel, we consider a Legendre function f admitting a minimizer T.. The preconditioning dramatically affect the convergence of DPGD. Indeed, if Vp Vf*, then DPGD algorithm converges in one iteration. To see this, note that in this case
x+ = x
Vp(0)] = Vy(0) V/*
if y = 1 and recall that V (0) is the minimizer of f (Proposition D. Of course, this preconditioning unrealistic since computing (() is as hard as minimizing
is more realistic to aim to find a preconditioner p that satisfies the following conditions.
Assumption (Dual relative smoothness). There exists L 2 such that
(Vp(x) Vply), x - y) s L(V ()* v), Vx,y E D(p).
(2)
Assumption (Dual relative strong convexity). There exists μ > such that
<Vp(>) Vp(v), r y) 2 (xV f v) Ya,y E D(p).
(3)
p and f* twice differentiable, these assumptions can be written
LV
for the ordering 3 of nonnegattvv matrices. These assumptions mean that Vp must be chosen close V in some sense. Moreover, they sufficient for the linear convergence of DPGD.
2

---

Under review as a conference paper at ICLR 2020
Theorem Maddissn al. (2019), Informal), If assumptioo 7 holds and if is Legendre, then the sequence of iterates of DPGD converges to 2, = arg min f. If asssuption 2 holds, then the convergence is linear.
In comparison, gradient descent (and many other first order methods, Nesterov (2018) converges for smooth convex functions/ f (i.e. functions f such that Vf is Lipschitz continuous). Moreover, the convergence is linear if is strongly convex. Many functions satisfy assumption I (and assumption 2 for some preconditioner p, without being smooth (or strongly convex), see Maddison et al. (2019).
If f is smooth and strongly convex, the convergence rate of gradient descent depends on the global condition number of f (defined as the Lipschitz constant of f divided by the strong convexity parameter). If к. is high, then the linear convergence of gradient descent is slow and is said ill-conditioned. The function f is said well-conditioned else. When f is ill-conditioned, it might be well-conditioned locally (i.e,, on small subsets of IRd) but the rate of convergence of gradient descent only takes into account the global, high condition number. This is not the case for preconditioned algorithms
[i & Malik (2016): Maddissn al. (2019).
SUPERVISED LEARNING SETTING
In this section, we describe our methodology to learn V.*.
3.1 FORMULATION
Our idea to sample points I; E D(J) according to some distribution and create the dataset ((V[(x); x;),, i E n.] where the v (xx)) represent the features and x; the labels. The feature space is D(f*) and the label space is D(f) (Proposition II. Since ff* maps V f fxz) to z (Proposition D ff* can be neural net to modelize ff. To solve our supervised learning problem, we design a machine learning algorithm. The goal of the training of the machine learning algorithm is to minimize the theoretical risk (0)
the solution of this supervised learning problem. We choose
L,) = Ex= (Valoddeel--(V(((.x).)))
where μ is the distribution of the labels X, represents the parameters of the neural network, Modelvy- (VS(X),) is the output of the neural network with input V and parameter 0, and
(V
is the loss associated to one sample (V)(
To fully specify the machine learning algorithm, we need fully define L, and the way we approxi- mate it. We proceed by
Choosing an architecture to specify the function Modelv (this is problem specific, see sections 3.2 4.2)
Giving value for μ (section 3.3
Providing way approximate the expectation in 4 by a finite (section 3.4)
Choosing loss & (this is problem specific, see section 4.2
Once this is done, the algorithm is trained using Stochastic Gradient Descent (SGD) (Bottou et al. (2018)).
3.2 GENERAL SETUP
In this section we give a general description of the map Modelvy-. According According to recommendations in Bengio 2012), we first standardize the features V Vf(x;) and the labels z, In other words, we apply a diffeomorphism (i.e, a one-to-one map which is continuously differentiable both directions) G D(f*) 0-5, 0.5]d to the features V fzx) and diffeomorphism H D(f) [-0.5, 0.5] to the labels z.. Then a neural network used to learn a predictor from the standardized features to the standardized labels, see figure T One obtain label from standardized label by applying the
3

---

Under review as a conference paper at ICLR 2020
inverse map H of H which can be easily computed (in practice H-1 is essentially addition
and multiplication by positive number), see section
Model vy"
Neural Network
H
V/(x)
vf)(e)
Figure 1: General model setup
3.3
CHOICE OF μ
We found that the choice of the distribution μ that parametrized L, is critical for the performance of the machine learning algorithm. The reason is the following. Recall that we want to learn Vf* to precondition DPGD algorithm whose goal to minimize nonsmooth and non-strongly convex (or ill-conditioned) objectives f, see section Let us imagine that we chose an uniform distribution for u.. Then, the situation in dimension one is represented by the figure
V((x)
Over-represented
Under-represented
Uniform sampling
Figure 2: The curve of V is typical of objectives / that we want to minimize
The image distribution v of by f over-represents some areas of the feature space while other are under-represented. When the distribution of the features is as degenerated v, it obvious that machine learning algorithms cannot generalize well (see [Bengio| (2012) Mesnil et al. (011T). Therefore, we have choose I carefully. The classical recommendation is to ensure that the input of the neural network (i.e the standardized features) are uniformly distributed (Mesnil et al. (201I). )). In other words, we have find js such that, x; μ4, then G V=(x;) is uniformly distributed over [-0.5, 0.5]d.
This can be done by using the change of variable formula.
Proposition Assume that f and f are differentiable. If μ is the distribution with density proportional to
[de((Jco))<z))
with respect to Lebesgue measure (where denotes the Jacobian matrix), then the distribution of Go (X() where X ps uniform over (-0.5, 0.5e
4

---

Under review as a conference paper at ICLR 2020
In the sequel. is the distribution whose density is given by Proposition Inspecting figure this seems reasonable since we expect X ~ y to have a high density when V slope is large and a low density when V f's slope is small.
Remark 1. worth noting that the evaluation of μ doesn't require any inversion as the inverse transform sampling technique. Besides, second order optimization algorithms usually require (an approximation of) the inverse of the Hessian matrix, which we don't need.
3.4 ESTIMATION OF THE LOSS
At this step, 1 is chosen and L, has to be minimized by SGD. As usual, Ly cannot be computed in closed form. The classical idea is to approximate Ln by an empirical mean involving samples from the distribution μ. Sampling from μ turns out to be difficult in our case. Indeed, the use of rejection-bert based MCMC methods lead to a high rejection rate. Since we can evaluate the density of μ. suggest to importance sampling instead.
Proposition If xz ~ π where the density of is positive, then
u(xx;) x(x;)
E Σ
(VMode) 0), m4)
(0),
where j(xx) (resp. (x)) denotes the density of p. (resp. π) with respect to Lebesgue measure.
We call the map 0 + 4 Σー (Mooelyy (V/(z;), 0), x4) [(..)
the empirical risk. Proposition
states that if x; т, then the empirical risk is an unbiased estimator of the theoretical risk. Since this estimator will be minimized using SGD, we only need know it up a constant factor. Therefore we
can get rid of the 1/n factor and of constant factors defining the densities of and æ. The distribution o is called the proposal distribution.
3.5 RELATED WORKS
Learning an optimization algorithm has already been proposed in the literature. In Li & Malik (2016); Andrychowicz et al. (2016) the authors propose to learn a better optimization algorithm by observing its execution over feature space of objective functions. This outperforms existing hand-engineered algorithms terms of convergence speed, but require to know the performance of some algorithms over some objectives. Using optimization literature knowledge, our approach allows to reduce the problem to supervised learning setting in IRd, that we can solve with neural net. In its philosophy, our approach can also be related deep learning methods for inverse problems used in signal processing, see e.g Lucas et al. (2018).
4 NUMERICAL EXPERIMENT
In this section, we run DPGD algorithm after learning Vf* We first consider a one dimensional toy problem with ground truth involving power functions as in Maddison et al. (2019). Then ill-conditioned logistic losses are considered. These functions cannot be minimized (efficiently) by gradient descent. We call LDPGD our approach (for Learned DPGD).
4.1 POWER FUNCTIONS AND LOGISTIC L.OSS
Two class of objective functions are considered. Power functions are defined by
(2, +00)
f x |r all", where
C E Rd
(5)
A is a matrix.
These functions are nonsmooth and non-strongly convex, therefore gradient descent is not guaranteed to minimize them. Power function minimization is the main example of Maddison et al. (2019).
We also consider the logistic loss
1 Σ
log (1 + exp (-b, (ax, x))) + T 1|0/1
f f: + n 1=1
(6)
5

---

Under review as a conference paper at ICLR 2020
where O and for every i, b, {-1,1]) and R These functions are strongly-conver and smooth. easy to control the condition number of f:
Lemma 1. Consider the logistic loss f and the matrix A whose lines are the as and denote Xmax the largest eigenvalue the real symmetric matrix A² A. Denote L, the smoothness parameter of and K. the condition number of f. Then,
Amax
Amax 4nr
L LS
+r, and K Σ
+ 1.
4n
4.2 EXPERIMENTAL SETUP
We use three layers neural network, with leaky ReLU activations and respectively 256 and 128 neurons in the two hidden layers. The square loss is used (y,,x) = lll z1|2 The proposal distribution for the importance sampling is taken gaussian. In the case of power functions, the features are rescaled using the map
log(1 + x) if
log-rescaling +
log(1 - x)) else.
Justification for this choice is provided in the appendix (section D Then the rescaled features and the labels are normalized to have zero mean and unit variance. The general architecture is summarized in figure
Model vy>
Input standardization
Neural Network
Output de-standardizatoon
Log-rescaling
Figure 3: Model with log-rescaling
The two first blocks correspond to the map G and the last block to the map H of section 3.2 The model is trained with a dataset of 1000 samples.
4.3 RESULTS FOR POWER FUNCTIONS
Consider f power function 5 where d = 1, = 50, == 50 and A is randomly chosen. We train the model during 100 epochs.
The next figure represents the performance of the machine learning algorithm we developped to learn f (note the scale of the inputs of V see section D
i.e, the Lipschitz constant V

---

Under review as a conference paper at ICLR 2020
Learning Curves
Grad
Traning
1000
Curput
Testing loss
Ground Truth
1500
750
1250
500
1000
700
-250
-500
250
-150
1e110
Figure Learning V Left: Learning curves. Right: predictions.
We that V is accurately learned the machine learning algorithm. This approximation of V f then used as a preconditioner of DPGD. The value the objective function and the value of the iteraaes while running LDPGD plotted the next figure. The stepsize is set to 1 during 10 steps and LDPGD is initialized at zo = 100.
Minimizing
LDPGO
16**
300
16
167
19
200
10
100
LDPGO
0
16
slaps
steps
Figure 5: Minimizing a one dimensional power function. Left: Objective function values. Right:
iterates values.
The iterates of gradient descent always diverge (no matter the stepsize choice). On the contrary, LDPGD iterates quickly converge to 357.1 (with (357..11) 3.8 x 10-14) which close to the actual minimizer (356.4 4 in this example).
4.4 RESULTS FOR LOGISTIC REGRESSION
Consider f logistic loss O6 with d = 50, n 1000, and condition number k. We train the model during 100 epochs. and represent the evolution the objective function and iterates while running LDPGD (after learning V and gradient descent (GD).
The algorithms are initialized at (50, 50, 50) and we use a stepsize for which GD converges linearly? This is done for several logistic losses with worsening condition numbers. To vary K. we vary the parameter r that controls the strong convexity of the objective f (see Lemma [ Intuitively, if r is high then f is well-conditioned and if is low f is ill-conditioned. The left figure represents the iterates (each curve corresponds to the evolution of one coordinate the iterates) and the right figure represents the objective fonction values while running both algorithms.
2GD converges linearly if the stepsize is smaller than 1/L, where I. is the Lipschitz constant of V.f Therefore, it is enough take stepsize smaller than 1/T where T/ is defined in Lemma
7

---

Under review as a conference paper at ICLR 2020
lteraes
Minimizing
40
50
LDGD
35
40
30
30
16
10
2000
6000
6000
10000
Figure Logistic regression with r == 0.5
harates
Minimizing
50
30
LDGD
25
05
20
10
10
step
Figure 7: Logistic regression with r 0.1
ttertte
Minimizing 1
50
LDGD
20
20
10
10
10000
step
Figure 8: Logistic regression with r = 0.05
Our careful preconditioning allows LDPGD to outperform GD especially when the objective is ill-conditioned, predicted by the theory, section 2
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Marcin Andrychowiez, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning learn by gradient descent by gradient descent. In Advances in neural information processing systems, pp. 3981-3989, 2016.
Yoshua Bengio. Practical recommendations for gradient-based training of deep architectures. arXiv e-prints, art, arXiv: 1206.533,, Jun 2012.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):22-331, 2018.
Ke Li and Jitendra Malik. Learning Optimize. arXiv e-prints, art. arXiv:1606.01888 Jun 2016.
Haihao Lu, Robert M. Freund, and Yurii Nesterov. Relatively-Smooth Convex Optimization by First-Order Methods, and Applications. arXiv e-prints, art. arXiv:1610.05708 Oct 2016.
Alice Lucas, Michael Iliadis, Rafael Molina, and Aggelos K Katsaggelos. Using deep neural networks for inverse problems in imaging: beyond analytical methods. IEEE Signal Processing Magazine, 35(1):20-36, 2018.
Chris J. Maddison, Daniel Paulin, Yee Whye Teh, and Arnaud Doucet. Dual Space Preconditioning for Gradient Descent. arXiv e-prints, art. 1eXiv:1902.02200 Feb 2019.
Grégoire Mesnil, Yann Dauphin, Xavier Glorot, Salah Rifai, Yoshua Bengio, Ian Goodfellow, Erick Lavoie, Xavier Muller, Guillaume Desjardins, David Warde-Farley, et al. Unsupervised and transfer learning challenge: deep learning approach. In Proceedings of the 201 International Conference on Unsupervised and Transfer Learning workshop- Volume 27, pp. 97-111. JMLR. org, 2011.
Arkadii Semenovich Nemirovsky and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
R. Tyrrell Rockafellar. Convex analysis. Princeton Mathematical Series. Princeton University Press, Princeton, N. J., 1970.

---

Under review as a conference paper at ICLR 2020
Appendix
CONTENTS
Infroduction
Background on dual preconditioning
2.1
Legendre functions
2.2
DPGD algorithm (Maddison et al. (2019))
2.3
Convergence theory of DPGD
3
Supervised learning setting
Formulation
3.2
General setup
3.3
Choice of /4
Estimation of the loss
3.5
Related works
Numerical experiment
4.1
Power functions and logistic loss
4.2
Experimental setup
4.3
Results for power functions
Results for logistic regression
Proof of Proposition
11
Proof of Proposition)
11
Proof of Lemmall
11
Log-rescaling
12
10

---

Under review as a conference paper at ICLR 2020
A
PROOF OF PROPOSITION 3
Recall that G is a diffeomorphism and that f Legendre. Let 2 the uniform distribution over [-0.5, 0.5 and denote g its density with respect to Lebesgue measure. Under the assumption of Proposition V D(f) + D(f*) is a diffeomorphism. Therefore, the map M = G V D(J) 0.5, 0.5] is also diffeomorphism and its inverse map is M V G
0.5. 0.5 + D(f). Our problem is to find distribution μ supported by D(f) such that M = G VX(X) X μ. Such j satisfies for every nonnegative measurable function Φ,
/ ((z))u(a) = 6(M (olr)oM()))ddpp (())dd((a)
-Ex=al(M o M(X))) -Ev
/ ((M)-(w))a(udd
J 6(M (M))) (Jt D(n) S PCn
((z)g( (e)
where Jay denotes the Jacobian matrix of M and the penultimate equality follows from the change of variable formula (which is allowed because M a diffeomorphism), Therefore, the only possible solution our problem is the distribution f with density proportional [-0.5, 0.5]d (which is always satisfied by definition of M) and O else. One can check that this density solves the problem.
if (xx)
B PROOF OF PROPOSITION 4
We apply the importance sampling principle the measurable nonnegative function (the parameter is fixed)
(xx) (VMooelly--V.(((tt)))))
We have
By (d()) = Ex
(6 (xx))
m(X) (X))
= E
1 Σ
μa(xz) π{Ι;)
i=1
where ~
C
PROOF OF LEMMA
Denote L the smoothness constant of f (i.e the Lipschitz constant of its gradient) and its strong convexity parameter. For every I E Rd
Vf(x) = n
brd:
+ exp (bi (a)) + ra
1=1
exp (b: (at, x²) (1 + exp (be (ai, )))
f²)(x)
b a
+ rla.
where La is the identity matrix. Note that for all + 1, [Ita]z S }. and that D3 < 1. It follows that
AT A
V2
+lla
4n
Therefore, - Amax +r. Since T./A, the result follows from the fact that S À (see Equation 6). 4n
11

---

Under review as a conference paper at ICLR 2020
D LOG-RESCALING
For power functions, V f(r) can range in [-10100, 10100] if is sampled from a gaussian. Assume d = that we use Doubles precision in the implementation. This means that all the values manipulate are stored with a precision of approximately 15 decimal places.
If we naively standardize (V (V(x))) to have zero mean and unit variance, we rescale numbers the range 1-10 10 1000o, to the range |-0.5, 0.3] This means that a precision of 10-16 the standardized scale represents precision of 10 in the original scale.
V/*
V
Input standarcization
10
Precision
10t5
10
Precision 10-15
In practice, this loss of precision means that inputs that are different before standardization, might be indistinguishable after the standardization. As result, the neural network might receive many different outputs for single input value.
4
Input stundardizatton
10
Precision
30
0.5
Precision 10
As it tries to minimize the empirical risk, the model will tend to associate input values average of the corresponding outputs. As a consequence, the regressed model will be a piecewise constant function, and will be constant on subsets of diameter 1086.
This is especially problematic for inputs close to 0. Let us denote No the neighborhood 0 on which the regressed model is constant equal Modely (0, 0). Any D(f) for which (z(x)) e No is a fixed point of the DPGD alogorithm:
1 Modelyy-(Vffla 0) Modely (0, (0)
x
I
Lp
1
[0]
I
Lp
The consequence is very undesirable: the solution offered by the DPGD alogorithm might æ even though (x(x) O(1085) is far from zero.
12

---

Under review as a conference paper at ICLR 2020
Model 8y"
Mo
V.00)
Figure Regressed model the imprecise dataset
As mentioned above, the lack of precision due naive standardization of the features is especially problematic around O. We therefore propose to preserve the scale around small values more than around large values. This can be achieved by applying the following transformation the features before normalizing them (to have zero mean and unit variance):
log(L 1 + x) if
log-rescaling:
log(1 [ x) else.
Log rescalicggng
0
2
-4
-100
-75
-50
-25
0
25
50
75
100
x
Figure 10: Log-rescaling.
13


Reviews:
[{"review_id": "SygFLpeAYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper attempts to learn a preconditioner for optimization, specifically for the Dual space preconditioned descent (DPGD). \n- The techniques used to learn the preconditioner are heuristic, not scalable and without justification or ablation studies. \n- It does not compare against \"standard\" optimization techniques that construct data-driven preconditioners such as Adam or Adagrad or even to more Newton, natural gradient methods that use the Hessian or the Fisher information matrix as preconditioners. It shows ad-hoc synthetic experiments in dimensions 1 and 50. This is clearly not enough. \nDetailed review below:\n- Section 2: Please explain why Legendre functions are useful in ML. For assumption 1, 2; it needs to be explained why these hold for a given f*. What constraints do you need on f? What functions satisfy these? Please explain this explicitly. \n- Section 3: What is the number of points x_i needed in high dimensions to learn? Is it even possible to scale up this method to high dimensions?\n- Constructing \\mu requires computing the determinant of the Jacobian. What is the computational complexity? Moreover, it seems that we need access to the \\nabla f(x) for all x in D(f)? \n- Please state all the assumptions in the beginning rather than introducing one at a time in the propositions. \n- Remark 1: It is unclear that the cost of an inverse Hessian matrix is more than the procedure proposed in this paper. \n- Section 3.5: Please explain what is the advantage of this learned optimizer compared to other methods? Note that there is literature on non-smooth optimization and methods like sub-gradient descent can be used in this case. \n- What is the justification for the selection of the loss function and log-rescaling?\n- The result of Lemma 1 is standard. Please acknowledge this. \n-  Section 4: \"The step-size is set to 1\". It seems that the optimizer has been overfit and engineered to work on this specific problem. Either these decisions need to be justified, there needs to be an ablation study or there needs to be a larger set of experiments. \n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HJetjtg0YB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[Update after rebuttal period]\nI have read the response,  my confusion in the original reviews cannot be answered satisfactorily. Therefore, I keep my initial scores.\n\n\n[Original reviews]\nFirstly, the motivation of the proposed method is not convincing for me. The authors want to propose a general methodology for learning precondition by supervised learning setting. However the method in practice, the x is a complex distribution, it is difficult to handle the map between the gradient and the x. This method proposes log-scaling, but it needs to be stored with a precision of approximately 15 decimal places and the regressed model will be a piecewise constant function, which is very computationally time-consuming.\n\nSecondly, the experimental results are not sufficient for evaluation. This paper shows two\nThe experimental result which includes the result of power function and the logistic function. But\nIt is not clear that the whole process of dual space preconditioned method with the model of computation of precondition given. And without quantitative results given, it is not convincing the “dramatic” speedups” of these methods, because the surprising training process is off-line and time-consuming. On the other hand, because of the different forms of the convex objective function, the network will train for the specific convex objective functions. In my opinion, it is not a general method to lead to dramatically speed up.\n\nFinally，the function of x and the gradient is complex, it is difficult to predict the relationship by using a simple network,\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkg2rQQZoH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an optimization method with the preconditioning in the framework of supervised learning. The ideal preconditioning is given by the Fenchel conjugate of the optimization function. This paper uses a supervised scenario to find the ideal preconditioning. The authors point out the importance of the sampling distribution then and propose a sampling scheme using the uniform distribution on the space of gradient descents. The samples are used to train neural networks that imitate the mapping of the Fenchel conjugate. The training network is incorporated into the Dual space Preconditioned Gradient Descent (DPGD). Some numerical experiments show the effectiveness of the proposed method comparing to the standard gradient descent method. \n\nThe authors proposed an interesting approach to the preconditioning in optimization problems. However, the paper is not well-written. In particular, the optimization algorithm is not clearly described. Numerical experiments with some toy problems are not very convincing to show the benefit of the proposed method. Though this paper may have some interesting ideas, more intensive analysis would be required. \n\nother comments:\n- The optimization algorithm is not explicitly described. Is the neural network trained as the batch learning? Is it possible to use the learning of the preconditioning in an online manner? \n- It is not sure whether the ideal distribution \\mu over the domain D(f) presented in Proposition 3 is computationally tractable. \n- In Proposition 3: I think that the uniform property of the sampling does not directly mean the optimality in the sense of the learning accuracy. The authors need to investigate the more detailed relationship between the distribution mu and the prediction accuracy of the Fenchel conjugate. \n- The proposed method requires the learning of neural networks, which will be computationally demanding. Please report the overall computational cost of the optimization algorithm in numerical experiments.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thanks for the detailed replies to the reviewers, which significantly helped us understand your paper better.
However, after all, we decided not to accept your paper due to weak justification and limited experimental validation. Writing should also be improved significantly. We hope that the feedback from the reviewers help you improve your paper for potential future submission.

Decision: Reject