Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values

Summary

In this paper the authors consider the problem of $\min_x f(x)$ with an order oracle that returns $sign (f(x)-f(y)+\delta)$ for some bounded noise $\delta$. The method is based on line search integrated with existing randomized coordinate update algorithms. Convergence rates on non-convex, convex, strongly convex objectives and its accelerated variant in the strongly convex case are provided. These are further extended to the stochastic setup $\min_x E_\zeta[f_\zeta (x)]$ with oracle $sign(f_\zeta(x)-f_\zeta(y))$ where a connection to normalized SGD is drawn and asymptotic convergence is derived. Numerical experiments are presented illustrating the performance of the proposed algorithms.

Strengths

The paper has clear exposition and adequately surveys the related literature. The problem under study is of great interest to the machine learning community and has many interesting applications. The technical claims are sound and presented ideas are conceptually simple with demonstrated good performance in several setting.

Weaknesses

I don't think the analysis result of "the convergence rate of random coordinate descent with the order oracle (OrderRCD), assuming minimal noise, is equal to first-order method random coordinate descent (RCD)" is surprising, given the algorithm is searching for best (1D) stepsize for coordinate update. And in this regard, neither is the acceleration result based on existing algorithmic framework. I've listed my main questions in the section below and here are some minor comments: - Line 77 is not finished. Line 78: it would be more clear if one could put in the argument in the norm instead of $\|\cdot\|$, which presumably would be on $x$? - It would be good to put the GRM in the main text otherwise Algorithm 1 does not make it clear how order oracle is used, which is the main focus of the paper. - Line 179: I'd suggest using a different letter for line search accuracy instead of $\epsilon$, which was used for denoting desired precision of the final optimization problem elsewhere. - In (8), it would be better to use the subscript $f_\zeta (x)$, which would make the notation more consistent with (1).

Questions

- Why is coordinate descent the best thing to do? To me, it seems like the order oracle is essentially a "noisy normalized gradient oracle". So while I can understand it is one way to incorporate the oracle information into existing method, is there any sense in which this is the optimal way to use this information? I think the paper will benefit from such a justification otherwise it seems rather ad-hoc. For example, why is coordinate update a good idea in this setup? Most zeroth-order methods do not seem to rely heavily on this (note that the oracle information is only used to select the stepsize in Algorithm 1). - Algorithm 1 as stated works on deterministic objective, i.e., it is not exploiting any finite-sum-type structure. If parts of the result do not concern stochastic objective, the authors should redefine their problem statement in (1). - The accelerated algorithm 2 has several loops, which makes me wonder how well it would be able to deal with noise in the oracle. - Similarly in Section 5, these reductions to existing methods are useful for getting some convergence guarantees, but is there a way to see this is how one should use the information optimally?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

Yes it's adequately addressed.

Summary

This paper addresses challenges in black-box optimization by introducing the concept of an Order Oracle. This oracle compares function values without assuming access to their actual values, allowing for the creation of new optimization algorithms. The paper proposes both deterministic and stochastic approaches, achieving SOTA convergence results and demonstrating the effectiveness of these algorithms through numerical experiments.

Strengths

1. The order oracle setting is new. 2. The theoretical analysis seems solid.

Weaknesses

1. Elaboration on Motivation: While the setting of the problem is interesting, the motivation for addressing this particular problem could be further elaborated, especially in the introduction. Providing a more detailed context and explanation of the significance and potential impact of solving this problem would help readers better understand its importance. 2. Comprehensive Experimental Validation: The experimental validation appears less comprehensive, as it relies on only one simple function. It would be much more convincing to apply the proposed method to the motivating problem outlined in the introduction. This would demonstrate the method's practical applicability and robustness in a real-world scenario. 3. Performance in High-Dimensional Space: I am curious about the performance of the proposed method in high-dimensional space, as this is often a significant challenge for coordinate descent methods. Could the author provide more insights or experimental results that address this aspect? If there are inherent limitations related to high-dimensional settings, it would be beneficial to discuss and highlight these issues. Providing such information would offer a clearer understanding of the method's strengths and potential limitations.

Questions

1. Technical Challenges compared to Nesterov's 2012 Work: I am curious about the specific technical challenges involved in the proof, especially in relation to extending and building upon Nesterov's 2012 work. Could the author provide more detail on the difficulties encountered and the novel techniques or modifications that were necessary to address these challenges? 2. Dimension-Independent Complexity: I notice that the paper presents a dimension-independent ($d$) complexity in comparison with existing works, as shown in Table 1. This is a significant and surprising result. Could the author elaborate more on this aspect? Specifically, I am interested in understanding the implications of achieving dimension-independent complexity. Or the dependence is manifested in some parameters.

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The author could discuss the limitations in high-dimensional space if this is indeed a constraint of the proposed method.

Summary

this paper focuses on solving the black-box optimization problem with order oracle method. specifically, the author provided a non-accelerated deterministic optimization algorithm, which relies on weighted sampling of the coordinate and the GRM method to resolve a linear search subproblem. the author provided convergence analysis on non-convex, convex and strongly convex cases and showing a superior iteration complexity. the author further an accelerated method called OrderACDM and proved its linear convergence. the stochastic case is discussed with asymptotic convergence results. Finally, the author provided a very simple numerical experiments to show the advantages of the proposed algorithms.

Strengths

1. overall, the paper is clear and easy to follow. 2. the author provided solid analysis to the convergence of the proposed algorithms and the results look correct to me. 3. the proposed algorithm looks clean and simple.

Weaknesses

1. i have some concerns on the novelty of this paper. in the non-accelerated algorithm, the two main techniques (the weighted sampling and the GRM) are not new. and the accelerated algorithm closely follows ( Nesterov and Stich, 2017). 2. both of the proposed algorithms are double loop algorithms as in each iteration, a linear search sub-problem is solved by GRM. as the author mentioned, GRM requires O(log 1/eps) iterations, which should be considered significant especially in the case of strongly convex problem. the author is hiding this factor with \tilde{O} in table 1, which makes the comparison unfair. 3. the numerical experiment is too simple. i understand this is a theoretical paper, but the experiments on a toy example is still below the bar of acception. 4. in the accelerated case, it's not clear to me how the proposed algorithm is compared with (ACDM), Nesterov and Stich, 2017) and (NU-ACDM), Allen-Zhu et al., 2016). the proposed algorithm looks slower to me since it is double loop. i would suggest the author to add more discussions on the convergence results. minor issues: 1. line 77, missing something after "to the inner product as.." ? 2. line 78, L_i appears before it is defined. 3. table 1, many parameters appear before they are defined.

Questions

1. in assumption 1.1, can L-coordinate-Lipschitz suggest L-smooth?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

see above

Summary

The paper considers the “Order Oracle” for optimization, which does not require the function values or gradient information, but only the relative ordering of the function values at different points. This can also be done with some small noise. This model captures the challenges encountered in real-world black box optimization problems and the authors motivate it via the ongoing developments in generative models. The main contributions of the paper are: 1. The paper provides SOTA convergence results up to log factors for deterministic algorithms with order oracle in the non-convex, convex and strongly convex settings. 2. The paper shows that acceleration in such an oracle is possible by giving an algorithm for strongly convex functions. They further show that the convergence results can be improved when the problem is low dimensional and compare it to the ellipsoid method. 3. The paper gives a stochastic version of the algorithm. The accelerated and unaccelerated algorithms are inspired by coordinate descent methods. The method is essentially coordinate descent where the step size is chosen via a specific line search procedure (golden ratio method) which is implemented using the order oracle. For the accelerated algorithm, the authors need to include a secondary line search to ensure that the iterates are always making progress.

Strengths

The paper demonstrates that using a very weak oracle such as order oracle is sufficient to get rates of convergence that match the rates of the optimal gradient methods via first order oracles. The algorithms are quite simple and work well in practice as shown in the experiments. The ideas are original and the results are presented clearly.

Weaknesses

The authors have motivated the use of this oracle, but it would be useful to have some concrete examples on how is it being used in practice.

Questions

1. When you say adaptive in the text, what does that mean? 2. The algorithms basically seem like you are performing coordinate descent, but instead of using gradients* step size, you want to directly compute this quantity using the GRM line search. So implicitly this is a first order method being implemented using an order oracle? If this is the case, is it possible to show an equivalence between the order oracle and gradient oracle? 3. What is the notation with $\alpha$? 4. Are there examples (even experiments) that can say something about the difference between the order oracle and usual first order oracles? 5. In the accelerated algorithm, are there adversarial examples where the second line search is necessary? 6. What is the barrier in extending the acceleration beyond strongly convex objectives.

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

The paper considers a weaker oracle model than what is usually considered in standard optimization results and gives algorithms under this oracle. It is not clear what the limitations of the oracle are from the paper, but the results match the ones obtained via stronger gradient oracles.

Summary

This paper explores the use of a zero-order oracle called the Order Oracle to solve optimization problems where exact objective function values are unknown. This oracle focuses on comparing the order of objective function values rather than requiring exact values.  The authors propose new non-accelerated algorithm, OrderRCD, that integrate the Order Oracle into coordinate descent algorithm and achieves performance comparable to state-of-the-art methods in non-convex, convex, and strongly convex settings. This involves randomly selecting coordinates and performing linear searches to find optimal step sizes. They also  present an accelerated optimization algorithm called OrderACDM, which uses two linear searches in each iteration to adaptively determine optimal step sizes. They show faster convergence rates and improved efficiency in strongly convex setting. The paper extends the concept to stochastic settings, showing asymptotic convergence. Numerical experiments validate the theoretical results, demonstrating that OrderRCD performs comparably to traditional methods, while OrderACDM converges faster, outperforming other methods.

Strengths

The paper formalizes a novel concept called Order Oracle, which enables optimization without requiring exact function values. Building on this concept, the authors develop two new algorithms, OrderRCD and OrderACDM, which integrate the Order Oracle into the coordinate descent framework. The paper provides a comprehensive theoretical analysis demonstrating the effectiveness of OrderRCD across non-convex, convex, and strongly convex settings and showing faster convergence rate of OrderACDM in strongly convex setting. The convergence proofs of both the algorithms are detailed. Additionally, this paper also introduce the first algorithm using the stochastic Order Oracle with asymptotic convergence guarantees. They also show practical effectiveness of OrderRCD and OrderACDM compared to traditional methods through their numerical experiments.

Weaknesses

The numerical experiments show the evaluation of OrderRCD and OrderACDM in standard quadratic functions. Experiments on real-world problems would strengthen the validation. The paper can include specific details about the numerical experiments, the exact values or structure of matrices and vectors $A$, $b$, and $c$, the dimensionality of the problems tested, datasets used etc. The paper does not deeply explore the scalability of the proposed algorithms in very high-dimensional settings or large-scale datasets. While the paper addresses stochastic optimization, analysis of noise sensitivity would enhance the understanding of the algorithm's performance under various conditions.

Questions

1. Could you provide more specifics about the numerical experiments? 2. Could you show numerical validation in real-world problems and datasets? 3. Are there any experiments being conducted for the stochastic order oracle? Could you show the results in that setting?

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

1. The theoretical guarantees rely heavily on the assumptions of strong convexity of the objective function. These assumptions may not hold for all types of optimization problems, limiting the applicability of the proposed methods to broader, less structured scenarios. 2. The paper does not provide practical demonstrations on large-scale, high-dimensional datasets. Additional experiments on a diverse set of objective functions and real-world datasets would provide a more comprehensive validation of the algorithms' performance and robustness 3. The accelerated version requires updating multiple parameters and has multiple steps and iterative processes that potentially increase the computational load. 4. In large-scale problems with high-dimensional data, the computational overhead from linear searches, parameter updates, and coordinate selections can become significant. The scalability of the algorithm is thus a concern, and its performance may degrade as the problem size increases.

On the rebuttal

I thank the authors for their responses to my questions. I have read the responses carefully and I am inclined to retain my original scores. And also, it must be interesting to see the algorithm in action real time, all the best to the startup!

reply to authors

I thank the authors for addressing my questions and concerns. Now i agree that the main contribution in this paper is to deal with a special case where only the order of obj function values can be accessed. I have increased my score to be 5. however, my main concern is still the design of the double loop algorithm that leads to an additional log factor and the experiments part. the author mentioned that they could add more practical experiment results. but those results may need another round of review in order to be considered.