Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity
Authors: Sally Dong
Haotian Jiang
Yin Tat Lee
Swati Padmanabhan
Guanghao Ye
Venue: NeurIPS 2022 Accept (2022)
Keywords: decomposable
non-smooth convex optimization
gradient oracle complexity
submodular function minimization

Abstract: Many fundamental problems in machine learning can be formulated by the convex program 
\[ \min_{\theta\in \mathbb{R}^d}\ \sum_{i=1}^{n}f_{i}(\theta), \]
where each $f_i$ is a convex, Lipschitz function supported on a subset of $d_i$ coordinates of $\theta$. One common approach to this problem, exemplified by stochastic gradient descent, involves sampling one $f_i$ term at every iteration to make progress. This approach crucially relies on a notion of uniformity across the $f_i$'s, formally captured by their condition number. In this work, we give an algorithm that minimizes the above convex formulation to $\epsilon$-accuracy in $\widetilde{O}(\sum_{i=1}^n d_i \log (1 /\epsilon))$ gradient computations, with no assumptions on the condition number.  The previous best algorithm independent of the condition number is the standard cutting plane method, which requires $O(nd \log (1/\epsilon))$ gradient computations. As a corollary, we improve upon the evaluation oracle complexity for decomposable submodular minimization by [Axiotis, Karczmarz, Mukherjee, Sankowski and Vladu, ICML 2021]. Our main technical contribution is an adaptive procedure to select an $f_i$ term at every iteration via a novel combination of cutting-plane and interior-point methods.


Decomposable Non-Smooth Convex Optimization with Nearly-Lineal Gradient Oracle Complexity"
Sally Dong
Haotian Jiang
Computer Science & Engineering University of Washington Seattle, WA 98195 sallyqd@uw edu
Computer Science & Engineering University of Washington Seattle, WA 98195
jhtdavid&uw, edu
Yin Tat Lee
Swati Padmanabhan
Computer Science & Engineering University Washington Seattle, WA 98195 yintat@ur.c edu
Electrical & Computer Engineering
University of Washington Seattle, WA 98195 pswati@uw.c edu
Guanghao Ye Department of Mathematics Massachusetts Institute of Technology Cambridge, MA 02142 ghye@mit. edu
Abstract
Many fundamental problems in machine learning can be formulated by the convex program
min
f(()),
DER
where each fü is convex, Lipschitz function supported on a subset of de coor- dinates of f. One common approach this problem, exemplified by stochastic gradient descent, involves sampling one f; term at every iteration to make progress. This approach crucially relies on notion uniformity across the fe's. formally captured by their condition number. In this work, we give an algorithm that minimizes the above convex formulation e-accuracy in Õ d, log(1/e) gradient computations, with no assumptions on the condition number. The previous best algorithm independent of the condition number is the standard cutting plane method, which requires (nd log log(1/e)) gradient computations. As a corollary, improve upon the evaluation oracle complexity for decomposable submodular minimization by [Axiotis, Karczmarz, Mukherjee, Sankowski and Vladu, ICML. 2021]. Our main technical contribution is adaptive procedure select term at every iteration via novel combination of cutting -lane and interior-point methods.
Authors ordered alphabetically.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Introduction
Many fundamental problems in machine learning are abstractly captured by the convex optimization formulation
minimizeggR* -i=1f(()
(1.1)
where each Si is a convex, Lipschitz function. For example, empirical risk minimization, each fi measures the loss incurred by the i-th data point from the training set. In generalized linear models, each ft represents a link function applicd to a linear predictor evaluated at the i-th data point.
The ubiquity of (1.1) in the setting with smooth fi has spurred the development of well-known variants of stochastic gradient methods [44, 7, 55, 6] such as [46, 49, 25, 35, 15, 36, 3, 22, 47]; almost universally, these algorithms leverage the "sum structure" of (1.1) by sampling, in each iteration, one fi with which to make progress. These theoretical developments have in turn powered tremendous empirical success in machine learning through widely used software packages such as 1ibSVM [13].
In many practical applications, (1.1) appears with non-smooth Si ss as well as the additional structure that each Si depends only on a subset of the problem parameters 0. One notable example is decom- posable submodular function minimization (SFM), which has proven to be expressive in diverse contexts such as determinantal point processes [30]. MAP inference in computer vision [29, 53, 17], hypergraph cuts [52], and covering functiins [50]. Another application is found in generalized linear models when the data is high dimensional and sparse. In this setting, fi depends on restricted subset of the parameters 6 that correspond to the features of the data point with non-zero value. Last but not least, the case with each f; depending on small subset of the parameters is also called sparse separable optimization and has applications in sparse SVM and matrix completion [42].
In this work, we initiate a systematic study of algorithms for (1.1) without the smoothness assumption'. Motivated by the aforementioned applications, we introduce the additional structure that each f; depends on a subset of the coordinates of 0. As is standard in the black-box model for studying first-order convex optimization methods, we allow sub-gradient oracle access to each ft.
Let J1. JI,.....,h functions, where each Ji depends on d; coordinates of 0, and is accessible via Jgradien oracle. Define m. := Ei= dj to be the "total effective dimension" " of the problem. Let
Problem 1.
: Rdd + TR be convex, I.-Lipschitz, and possibly non-smooth
rr = arg mingeR* Σi= fi(8) be minimizer of (1.1), and let ((0) be an initial point such that |10(0) - 1-112 S R. We want to compute vector 0 E Ee satisfying
Σ 1100s S SLR+ E(00).
(1.2)
Prior works. We focus on the veakly-polynomin regime and therefore restrict ourselves to algorithms with polylog(1/e) gradient oracle complexities. Table summarizes the performance of all well-known algorithms applied to Problem 1. Note that the variants of gradient descent each require bounded condition number. The results of [39, 2] and cutting plane methods are all complemented by matching lower bounds [54, 40]. Additionally, the work on non-smooth ERM crucially requires the objective function to be a sum of a smooth ERM part and non-smooth regularizer. There are many important problems for which the objective function cannot be split in this way, for these problems, the techniques developed for non-smooth ERM do not apply. In comparison, our work can be understood as dealing with a more general ERM problem with fewer structural assumptions.
Even with smooth fi's, first-order methods perform poorly when the condition number is large, or when there is a long chain of variable dependencies. These instances commonly arise in applications; an example from signal processing is
minimize,
(xi - 1)
Σ (x;
x
+ x2 {
(1.3)
"In decomposable submodular minimization, each fo corresponds to the Lovász extension of the individual submodular function and is therefore generally non- smooth.
A function f is said to be 3- smoothh if fw) < f(x) + (Vf(x). y x) + +//21ly - æ13 for all 2, and Re-stronglycoonven if f(y) 2 f(x) + (Vf(x) - 2) + a/21ly - z for all x, y. The condition number of f is defined to be 3/a.

---

Authors
Algorithm Type
Queries
Non-smooth OK?
[12]
Gradient Descent (GD)
O(ue log(1/o)
[39]
Accelcrated (Acc.) GD
O(ng (1g(//)))
[46, 49, 25]
Stochastic (Stoch.) Rrhance-Reducedd GD
((in + R) log (1g()
[48, 34, 18,
Acc. Stoch. Reduued GD
((n v(RR) log(R) (og(1/))
[2]
Ace. Stoch. Pariance-Reduced GD
O( vnne log(1/e))
[27, 37,3,,,,3
C'utting-Plans Method (CPM)
O( Ongdlog( l//()
[31, 16]
Robust Interiur-Pott Point Method (IPM)
oi d (og(1/c)
Table 1: Gradient oracle complexities for solving (1.1) to e-additive accuracy. denotes the condition number of Σ; fi. and R is variant of the condition number defined to be the sum of smoothness of the fi's divided by the strong convexity of Σx J.-
whose variables form an O(n)-lentth chain of dependencies, and has condition number x: ( and R = (nn²). Gradient descent algorithms such as [39] and [2] therefore require (2n²²) gradient queries, despite the problem's 's total effective dimension being only (n)).
On the other hand, outting-plane methods (CPM) and robust interior-point methods (IPM) both trade off the dependency condition number for worse dependencies on the problem dimension.
These significant gaps in the existing body work motivate the following question:
Can we solve Problem using nearly-linear (in total effective dimension) number of sub-gradient oracle queries?
In this paper, we give an affirmative answer to this question.
1.1 Our results
We present an algorithm solve Problem with gradient oracle complexity nearly-linear in the total effective dimension. Our main result is the following theorem.
Theorem 1.2 (Main Result), Given Problem I and ((0) such that ||0 -8(0) fi are L-Lipschitz, then there an algorithm that in time poly log(1/e)), using O(m log(m/e)) gradient oracle calls, outputs a vector E RRd such that
||2 S R. Assuming all the
a Σ f100) S Σ +(00)+++ LR.
Intuitively, the number of gradient queries for each f. should be thought of as (cd,) in our algorithm, which nearly matches that of the standard cutting-plane method for minimizing the individual function overall obtained by leveraging the additional structure on
fi. The nearly-linear dependence the Ja's and stands in stark contrast to the O(n)) query complexity of CPM, which is significantly worse in the case where each d, < d. Furthermore, we improve over the current best gradient descent algorithms in the case where the f. have a large condition number.
Based the query complexity of the standard cutting- -aanne method, have the following lower bound matching our algorithm's 's query complexity to a log m-factor:
Theorem 1.3. There exist functions fi...., fn IRd + IR for which a total of Q(m ())) gradient queries required solve Problem 1.
An immediate application of Theorem 1.2 is to decomposable submodular function minimization:
Theorem 1.4 (Decomposable SFM). Let V = 21, and F 2V + [-1, 1] be given by F(S) = E.EIE((S V.), where each F. : 2%. IR is a submodular function on V, S V with IVil k. We can find e-additive approximate minimizer of F in O(nk2 log(nk/e)) evaluation oracle calls.
Theorem 1.4 significantly improves over the evaluation oracle complexity of Ō(kk log(1/e) given in [4] when the dimension & of each function F, is large. For non-decomposable SFM, i.c. n and

---

| - k. the current best polyyoplo time SFM algorithm" finds an e-approximate minimizer in time O(k² [og( [33]. Therefore, our result Theorem 1.4 can be viewed as a generalization of the evaluation oracle complexity for non-decomposable SFM in [33], and the dependence on k in Theorem 1.4 might be the best possible. We defer the details of decomposable SFM to Appendix D.
1.1.1 Limitations
Some limitations of our algorithm are as follows: When each f. depends on the entire d-dimensional vector 0, as opposed to a subset of the coordinates of size d; < d, our gradient complexity simply matches that of CPM. We would like to highlight, though, that our focus is in fact the regime d, < d. When the fi's are strongly-convex and smooth, our gradient complexity improves over Table only when K is large compared to d; Finally, note that we consider only the gradient oracle complexity in our work; our algorithm's s implementation requires sampling a Hessian matrix and a gradient vector at every iteration, which incur an additional poly(m, log(1/e)) factor in the overall running time.
1.2 Technical challenges in prior works
We now describe the key technical challenges that barred existing algorithms from solving Problem 1 in the desired nearly-linear gradient complexity.
Gradient descent and variants. As mentioned in Section the family of gradient descent al- gorithms presented in Table are not applicable to Problem 1 without the smoothness assumption. When the objective in Problem 1 is smooth but has large condition number, even the optimal deterministic algorithm, Accelerated Gradient Descent (AGD) [39] can perform poorly. For example, when applied to (1.3), AGD updates only one coordinate in each step (thereby requiring n steps), with each step performing n gradient queries (one on each term in the problem objective), yielding a total gradient complexity of (n²²) [39]. For a similar reason, the fastest randomized algorithm, Katyusha [2] also incurs a gradient complexity of ((n²)) [54].
sotting-plane methods (CPM). Given a convex function ff with its set S of minimizers, CPM minimizes f by maintaining convex search set g(k) 2 S in the hth iteration, and iteratively shrinking ((k using the sub- uub-gradients of f. Specifically, this is achieved by noting that for any x()
chosen from g(k), the gradient oracle indicates (x((()) K O, (i.e. (1) & S), then the convexity
of f guarantees S S (())) == {y: (x)(x()),, y x-xt x S SO). and hence S S (()) n g(),, The algorithm continues by choosing g(k+1) 2 g(R) n 7((,,, and different choices of x and gk) yield different rates of shrinkage of (1)) until a point in S is found.
Solving Problem via the current fastest CPM [24] takes Ö(d) iterations, each invoking the gradient
oracle on every fi to compute V (x(())) = Σ overall, which can be quadratic in n when d = V (x)) This results in ((d) gradient queries θ (n) even if each fi depends on only d, = O(1) coordinates. Similar to gradient descent and its variants, the poor performance of CPM on Problem 1
may therefore be attributed to their inability to query the right f; required to make progress.
Interior-point methods (IPM). IPM solves the convex program miDues(c, u) by solving se- quence of unconstrained problems min, (u) == (t- (c. u) + (u() parametrized by increasing f, where shs is self-concordant barrier function that enforces feasibility by becoming unbounded as it approaches the boundary of the feasible set S. The algorithm starts at O, for which an approximate minimizer xi of the is known, and alternates between increasing & and updating to an approximate minimizer x; of the new V. via Newton's 's method. For a sufficiently large t, the minimizer x also approximately optimizes the original problem millue (c, u) with sub-optimality gap (v)/t,, where v is the self self-concordance parameter of the barrier function used.
To apply IPM to Problem 1, we may first transform (1.1) to min(nx Σ, z, where K = { z) (u,, 2.) E K.,, Vi E [n]] and KG = {u, 2:) f(, S 2:) is the feasible set. Using the universal barrier the for each KG; [38], the number of iterations of IPM is Ö di), each requiring the computation of the Hessian and gradient of v/; for all E [n]. leading to a total of (65 sub- gradient queries to f 's even when all d; 0(1. Even when leveraging the recent framework of
'Here, focus on the weakly-polynonee regime, where the runtime dependence on e is log(1/e).

---

robust IPM for linear programs [31]. the computation of each Hessian (by sampling the corresponding KG [23]) yields total sub-gradient oracle complexity of Ó(Σi=) de-s), ), far from the complexity we seek.
1.3 Our algorithmic framework
We now give overview of the techniques developed in this work to overcome the above barriers. First, by making identical copies of coordinates shared by different f, and using the convex sets IC2 to make the objective function linear, transform (1.1) into convex program over structured convex sets:
minimize subject to
(c, x),
x; E Kg C Rd.+1
Vi E [n]]
(1.4)
Ax b.
where x is the concatenation of the vectors X1,..., Xn, the objective vector c is for the last coordi- nate of each x; and 0 otherwise, and Ax = b enforces that different copies of the same coordinates should be the same. Note that the sub-gradient oracle for Si can be transformed equivalently to a separation oracle K,,. We define K. == Ki K2 ... K...
Main idea: combining CPM and IPM. Recall that CPM maintains a convex set which initially contains the feasible region and gradually shrinks around the minimizer, while IPM maintains point inside the feasible region that moves toward the minimizer. Our novel idea is to combine both methods and maintain an inner convex set Km, as well as an outer conver set Kout, for each i [n]] such that Kin.i S K. S i. We define Kin and Kout analogously to IC. When Inequality (3.4) and Inequality (3.3) are satisfied for all i [n], we make Ity-lt updates without needing to make any oracle calls. When Inequality (3.3) is violated for some i E [n]. we query the separation oracle at the point x defined as the centroid of Kout, (c.f. Proposition 3.2). Based on the oracle's response, we iteratively either grow Kin,; (and, thus, Kin) outward or shrink Kout,, (and, thus, Koaa) inward, until ultimately they approximate K. around the optimum point.
large change in volume. If the point X violates Inequality (3.3) for some i E [m]. we query the separation oracle to see if x E KC; or not. If Xoun. E K,, then it is used to expand Kin. yielding in a large volume increase for Kin,s- On the other hand, if X é K., the fact that it is the centroid of Kout,; results in large volume decrease for Kout, when it is intersected with a halfspace through X Thus, our algorithm witnesses a large change in volume of one of Kan. and Kout, regardless of the answer from the oracle. Just like in standard CPM, this rapid change in volume is crucial to achieving the algorithm's oracle complexity.
First benefit:
Second benefit: making smart choice about querying ft. Since the algorithm maintains both an inner and outer set approximating I. by checking if Knn, and Kout,s differ significantly (Inequality (3.3) essentially performs this function), we can determine if K.; is poorly approximated, and if so, improve the inner and outer approximations of the true feasible set. Choosing the right K;; translates to choosing the right fi make progress with at an iteration; thus, we address the central weakness of the gradient descent variants in solving (1.1).
2 Notation and preliminaries
The full version of the preliminaries required understand all proof details in Appendix A.
We use lowercase boldface letters to denote (column) vectors and uppercase boldface letters to denote matrices. We use x, to denote the 7th block of coordinates in the vector x (the ordering of these blocks is not important in our setup).
We use (x,y y) to mean the Euclidean inner product x A subscript in the inner product notation means is induced by the Hessian of some function (which is locally specified) at x; for example, V xx)v with & separately specified. We define the local norm of v at x analogously:
(u, v)x
||v|| / (v, 2 v). We also define the norm ||v||x,| == El_ ||
We use 1ab to represent barrier functions and + to represent potential functions, with appropriate subscripts and superseripts to qualify them needed.
5

---

Definition 2.1 (Polar of Set). Given a set S _ R"", its polar is defined as
S = ty xy,x) S 1, E).
Lemma 2.2 (145)), Let S S. Rn be a closed, compact, convex set, and let y be point. Then (conv {) S n H. where H is the halfspace defined by H {z E R": (2, $1}.
Theorem 2.3 ((20, I1]). Let f be a log- oo-cconavee distribution on R with centroid cj. Let H. {u E RR (u, v) 2 }} be halfspace defined by normal vector v Rd. Then, Sx f(z)dz Z t", where i. VEy--(vo--ap1 is the distance of the centroid the halfspace scaled by the
9- (-(e)
standard deviation along the normal vector v and t == ma t}.
Definition 2.4 (Self-concordance)) We call F Q + IR self-concordant function convex set Q for any x E Q and any h,
[x)(x) h, 2()*F(x)[h, h))
where D*F((x) F(x) hig the k-th derivative of F along the directions hi...., ... h,. Addi- tionally, if for any x E Q, we have (F( (V) barrier.
v, then F is u-self-concordant
Finally, we need the following definitions of entropic barrier and universal barrier.
Definition 2.5 ([10, 14]). Given convex body A. _8"h and some fixed 0 E R", define the function
f(0) log [xxcx. exp(x, d) Then the Fenchel conjugate f* int(KC) - IR is self-concordant barrier termed the entropic barrier. The entropic barrier c-seelf-concordant.
Definition 2.6 ([41, 32]). Given a convex body IC [ R", the universal barrier IC is defined as v (n.( + R by
(xx) log vol((K (IC x)%)
The universal barrier is csnff-cconoodant.
Our algorithm
We begin by reducing Problem to the following slightly stronger formulation (see Theorem 1.2 for the detailed reduction):
minimize subject to
(c, x), x; E KG C Rd vi [n]
(3.1)
Ax
where x is concatenation of vectors x, 's, and the K,, 's are disjoint convex sets. This formulation decouples the overlapping support of the original fi's by introducing additional variables tied together through the linear system Ax b. Each Kc; constructed by applying a standard epigraph trick to the function fi-
Note that we do not have closed-form expression for KG, Instead, the subgradient oracle for fa translates to separation oracle for KG; on a point queried by the oracle, the oracle either asserts z; E K,, returns separating hyperplane that separates z; from K,,
At the start of our algorithm, we have the following guarantee:
Lemma 3.1. At the start of our algorithm, we are guaranteed the existence of the following.
Explicit convex sets Kin = Kin,1 Kin x ... Kinn and Kout == Kouu,1 X Kout, Kout. such that Kr,, K Ki X ... x Knn C Kout
2. An initial Xinitiat E Kin such that AXinitial = b.
We show how construct such set Kin in Appendix C. and how to find such Kout and Xinitial in Appendix C.2.

---

Algorithm Minimizing Decomposable Convex Function
1: Solving Problem 3.1
2: Input. 6, A, b, c, R, m n, X, Kins Kout, and O for each i [n].
8m 3: Initialization. /. = in log mn and lend clelaat ! 100 and X (via Equation (3.2))
4: while true do
5: if (c. x) I Xou) + 4m then
> Either update t or end the algorithm
6: ift tend then
7:
return arg min (t(c, + E (m
End the algorithm
8:
end if
9:
t t. [1+
7
>i Update t Xut computed as per Equation (3.2)
4m
10:
Update Xou and jump Line 4
11:
end
for
all E [n]] do if (V ( X - x.) + nl|xxou.. - x; xilix: 2 4d; then if x K; then
13:
Query O Update Kin,
15:
Kin.i conv (Kin;; Xonl.)
16:
else
17:
Kout, Kout, Hi where H4 (x(xin))) end if
Update Kout,
18:
Update X and jump Line 4
Xuu computed as per Equation (3.2)
20:
end
end for
22:
Set 6x = 2
Xu- where ||u||x,1 == E ||u//x/
| -
23:
x &x
D. Move towards X
24:
end while
3.1
Details of our algorithm
In this section, we explain our main algorithm (Algorithm 1).
The inputs to Algorithm are: initial sets Kin and Kout satisfying Kin C IC S Kours an initial point Kin satisfying Ax b, separation oracle O for each K,, the objective vector c, and scalar parameters m, n, R, r. and e. All the parameters are set in the proof of Theorem B.
Throughout the algorithm, we maintain central path parameter for IPM-inspired updates, the current solution x, and convex sets Kin.i and Koutt, satisfying Kin,i S K. S Kout,, for each i [m]. To run IPM-style updates, we choose the entropic barrier on Kour and the universal barrier Kin-
Given the current set Kaut, the current t,, and the entropic barrier thout defined on Rum = Kout n (u Au = b), we define the point
X arg min {l(c, + thmm x
(3.2)
Per the IPM paradigm, for the current value of t, this point serves a target "chase" when optimizing (c, x) over the Rour- Although our overall goal in Problem 3.1 is to optimize over [u Au b}. we do not know K. explicitly and therefore must use its known proxies, Kün or Kouti we choose Kout because Komt 2 K. ensures we do not miss a potential optimal point.
Having computed the current target x we move the current solution x towards it by taking Newton step, provided certain conditions of feasibility and minimum progress are satisfied. If either one of these conditions is violated, we update either Kan Komt or the parameter t.
Updating x. In order to move x towards x require two conditions hold: x Kr, and (c, 2 (c. X + O(1/t).
The first condition implies x E K., which would in turn ensure feasibility of the resulting after Newton step. To formally check this condition, we check the following inequality is satisfied for all i [n]] and for fixed constant ?/:
(Vr'm Xam. x2) 77 ||xSun. xillx; S 4d,,
(3.3)

---

The intuition is that since any point within the domain of self-concordant barrier satisfies the inequalities in Theorem A.5 and Theorem A.6, violating Inequality (3.3) implies that x is far from Kin,i, and as result, X.ur is not good candidate to move x towards.
The second condition we impose, one of "sufficient suboptimality", ensures significant progress in the objective value can be made when updating x. Formally, we check if
4m
X
<..x.
(3.4)
If the inequality holds, then there is still "room for progress" to lower the value of (c, x) by updating x; if the inequality is violated, we update & instead.
Given the two conditions hold, we move x towards X in Line 23. The update step is normalized by the distance between x and X measured in the local norm, which enforces x E X. (since by the definition of self-concordance, the unit radius Dikin ball lies inside the domain of the self-concordance barrier), and also helps bound certain first-order error terms (Inequality (B.14) in Appendix B.3).
The rest of this section details the procedure for when either of these conditions is violated.
Updating the inner and outer convex sets. Suppose Inequality (3.3) is violated for some i E [m]. Then Xouta & Kin.á which in turn means x might not be in the feasible set K. To reestablish Inequality (3.3) for i, we can either update Kin,i, or update Kout, and compute a new XauLi by Equation (3.2).
To decide which option to take, we query O₂ at the point x if the oracle indicates that x &.,, then we incorporate oon, into Kin,s by redefining Kin.i = conv conv(Kim, xonta) to be the convex hull of the current Km. and X (Line 15). If, on the other hand, x & K,,, the oracle O, will return halfspace Hi satisfying H4 2 KC; Then we redefine Kout. Kouut, nHZ (Line 17). After processing this update of the sets, the algorithm recomputes X and returns to the main loop since updating the sets does not necessarily imply that the new x satisfies X.ut E Km.
This update rule for the sets is exactly where our novelty lies: we do not arbitrarily update sets, ruther, we update one only after checking the very specific condition Xout, $ Kinns Since the separation oracle is called only in this part of the algorithm, performing this check enables to dramatically reduce the number of calls we make to the separation oracle, thereby improving our oracle complexity.
Further, this update rule shows that even when we cannot update the current x, make progress by using all the information from the oracles. Over the course of the algorithm, we gradually expand Knn and shrink Kout. until they well-approximate K. To formally quantify the change in volume due to the above operations, we consider the following alternative view X
Proposition 3.2 (Section 3 in [10]: Section of [28]). Let 0 R", and let po be defined as (x(x) == exp((0, x) - f()), where f(f) == log [s exp((() u))du]. Then,
Ex-po [x] arg min (f (0, x)}
(Kint(K))
By this proposition, x defined in Equation (3.2) satisfies
X E
exp(-r(c.u))du)) [x],
(3.5)
that is, X is the centroid of some exponential distribution over E As a result, if x & Kr, the hyperplane cutting R... through x will yield a large decrease in volume of Roats per Remark 9. Therefore, the query result in a large change in volume in either Knn or Kout allowing us to approximate I. with a bounded number of iterations.
Updating t. If Inequality (3.4) is violated, then the current x is "as optimal as one can get" for the current parameter t. This could mean one of two things:
The first possibility is that we have already reached an approximate optimum, which we verify by checking whether > O(1/e) in Line 6: If true, this indicates that we have attained our desired suboptimality, and the algorithm terminates by returning
Σ vin:(x:) }. 1=1
x ret = arg
min Ax=b
t. (c,x) +
8

---

The point x""* is feasible because it is in Ii by definition, and the suboptimality of ((1/tead) = O(e) ensures it an approximate optimum for the original problem.
The second possibility is that we need to increase to set the next "target suboptimality". The value of is increased by scaling factor of 1 + O(1/m) in Line 9. This scaling factor ensures, like in the standard IPM framework, that the next optimum is not too far from the current one. Following the update to recompute X by Equation (3.2). Since (c, x) (c, x (L//t) is not guaranteed with the new and X the algorithm, jumps back to the start of the main loop.
Our analysis
To analyze the oracle complexity of Algorithm 1, define the following potential function that captures the changes in Kin, Nout, i, and x each iteration:
+ = t(c, + log J
JR.. exp( stc d)
(x;),
(4.1)
EE
entropic terms
universal terms
where log JR_.. exp(-t(c, u) )du is related to the entropic barrier on Rour (see Appendix B.1) and tiin is the universal barrier on Kin We have the following bounds on the change in potential when Kin.. Kout,.i t, and x are updated respectively; the formal statements are found in Appendix B. Appendix B.2, and Appendix B.3.
Lemma 4.1. Let be a fixed vector. Let d be the potential given in Equation (4.1), defined as function of Kin Kontt x, and Following an update one of the parameters while keeping the others fixed, we have the following bounds on the new potential @lnew);
1. Let Hi be the halfspace generated by the separation oracle On queried X shown in Line 17 of Algorithm 1. Then the new potential (p/nww defined with respect to Row O Hi is bounded by ((nww)
< + log(1 1/e).
When is updated to to respect to the updated is bounded by
[1+ a
in Line of Algorithm 1, the new potential ((now) defined with
4m
To (new)
< x
3. Given a convex set K. S TRd and a point x E K. let v/x == log vol(K. - x) be the universal barrier defined on K. with respect x. For some fixed n 1 1/4, let y K. be point satisfying
(Vix(xx) x) nlly =x|x 2 4d,
(4.2)
and construct the new set conv (K. Then, the value of the universal barrier on the new set with respect to x satisfies
(conv((.x))x) (x) xxx(x)) + log(1 1/e + +)-
Consider the update step 8x X ||xi,x x as Line 22. Assume the guarantees in Inequal- ity (3.3) and Inequality (3.4). Then the new potential @ineww defined with respect the updated is bounded by
1/2 4
(neww) < $
Proof sketch. We use tools from convex analysis, self-concordance calculus, and Grünbaum's 's results to derive the above potential bounds, as explained below.
Consider the update of R.m to Romi O His with Hi passing through X Recall from Equation (3.5), x is the centroid of Rau with respect the (log-concave) distribution exp xt) - log Jk_.. exp(-t u)) ud)du] Therefore, per Remark 9, the volume of &... nH; most - 1/e factor of the volume the original R.m. which translates to the claimed potential change.

---

2. The change in & by updating to t. (1 + h) for some h > is
(lnew) ① -0 log
V exp(-t(1+ h)c, v)dr log U expl-te, v)dr cxp
} th (c,x).
Run
(4.3)
To bound the right-hand side, the key observation is that by duality with respect to the entropic barrier (Definition 2.5), the function log [KEER.. exp((x, 0) )dx] is also self-concordant. This in turn allows us to bound the difference between the first two terms in the right hand side of Equation (4.3).
3. Lemma 2.2 implies (conv(K, -) ()- nH. where H. = {z E I= (2,y - x) & 1}. Therefore ())) (x) (x) may be bounded via the change volume of set after intersection with halfspace, for which we can again apply Grünbaum's ss result (Theorem 2.3). To argue that the halfspace H. cuts the set (K-x) at a point not too far from the centroid of (K x)" we use the intuition that any satisfying Equation (4.2) must be far from K, by properties of the self-concordant function t/c. This means conv (K, y) is much larger than K., giving the desired conclusion by duality.
The change potential due to change x as per the stated update rule is given by
T (new)
Wx,,s(x; 8x,5) wimms (V (x)), 5x,1)l
The term in the summation on the right-hand side measures the error due to the first-order approxima- tion of than around x,, which can be bounded by self-concordance. To bound the remaining linear term, we use V t tc Σm= Vthm,((;;) and the assumed inequalities.
By adding all the potential changes shown in the above lemma and using the bounds we derived on lower and upper potentials (c.f. Lemma B.8), we show (c.f. Lemma B.9) the oracle complexity of Algorithm to be (m log oracle complexity of Problem 3.1 (c.f. Theorem B. 10) and that of Problem (c.f. Theorem 1.2). The full details of this may be found in Appendix B.4.
m ) Combined with our results on initialization then yields the
er
4.1 A remark on implementability
The gradient and hessian of the entropy barrier are the centroid and covariance of some exponential distribution over polytope. In our setting, we need only constant factor approximation of these quantities. While sampling from log-coneave distribution in general takes n1..2 time, in our case, sampling from an exponential distribution over explicit sparse polytope is faster, taking around quadratic time in practice because of our assumption that each fi depends only on a few variables.
These results (and runtime complexity) of sampling from an exponential distribution over explicit polytope have practical motivation as well, for example, in simulating metabolic networks (which can contain hundreds of thousands of variables) in bioinformatics. As result, there has been extensive work developing new software for this task. One such popular package is https: ht///pppccob/// github. / cobratoolbox// bttttooooooo/tbbee//oo///oo stable/. It can sample from polytope with tens of thousands of variables currently in seconds. This package includes ACHR, CHRR, RHMC, all representing three generations of improvement on the sampler in last 20 years. For example, for one human model (RECON3) with 12k variables, ACHR probably takes 10th epu-sec to obtain one sample from that polytope while CHRR takes 10t cpu-sec and RHMC takes 30 sec.
Therefore, even though the focus of our work has been on developing the theory, the preceding discussion suggests that there could be an implementation of our algorithm which can perform reasonably well in practice.
Acknowledgements
We thank the anonymous reviewers of NeurlPS 2022 for very helpful comments. Research of YL is supported by NSF awards CCF-1749609 DMS-1839) 16, DMS-2023166 CCF-2105772, Microsoft Research Faculty Fellowship, Sloan Research Fellowship, and Packard Fellowship. The full version of this paper is available at https : //tpx//xxvvv////////////////aa wtg/pdf//// /2200 03811.pdff
10

---

References
[1] Alckh Agarwal and Leon Bottou. A lower bound for the optimization finite sums. In International conference machine learning, pages 78 86. PMLR, 2015.
[2] Zeyuan Allen- Katyusha: The first direct acceleration of stochastic gradient methods. The Journal of Machine Learning Research, 18(1):8194-82) 2017.
[3] Zeyuan Allen-Zhu and Yang Yuan. Improved svrg for non-strongly-conner or sum-of-non- convex objectives. In International conference on machine learning, pages 1080-1089. PMLR, 2016.
[4] Kyriakos Axiotis, Adam Karczmarz, Anish Mukherjee, Piotr Sankowski, and Adrian Vladu. De- composable submodular function minimization via maximum flow. In International Conference on Machine Learning, pages 446-456. PMLR, 2021.
[5] Dimitris Bertsimas and Santosh Vempala, Solving convex programs by random walks. In Proceedings of the thiry-fourth annual ACM symposium Theory of computing (STOC), pages 109-115, ACM, 2002.
[6] Léon Bottou. Stochastic gradient descent tricks. In Neural networks: Tricks of the trade, pages 421-436 Springer, 2012.
[7] Léon Bottou and Yann Cun. Large scale online learning. Advances in neural information processing systems, 16, 2003,
[8] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[9] Silouanos Brazitikos, Apostolos Giannopoulos, Petros Valettas, and Beatrice-Helen Vritsiou. Geometry of isotropic convex bodies, volume 196. American Mathematical Soc., 2014.
[10] Sébastien Bubeck and Ronen Eldan. The entropic barrier: a simple and optimal universal self-concordan barrier. In Conference on Learning Theory, pages 279-279, 2015.
[11] Sébastien Bubeck, Bo'az Klartag, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. Chasing nested convex bodies nearly optimally. In Proceedings of the Phirty-First Annual ACM-SIAM Sympo- sium on Discrete Algorithms, pages 1496-1508. 2020.
[12] Augustin Cauchy et al. Méthode générale pour la résolution des systemes l'équuation simul- tanées. Comp. Rend. Sci. Paris, 25(1847):536-534 1847.
[13] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1-27:27, 2011. Software available at htwt://www... wwwe. ntu. edu, tt/""j/innliiibiii /ibbvmm.
[14] Sinho Chewi. The entropic barrier is n-seef-concordaat. arXiv preprint 17X9 2021.
[15] Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradi- ent method with support for non-strongly convex composite objectives. Advances in neural information processing systems, 27, 2014.
[16] Sally Dong, Yin Tat Lee, and Guanghao Ye. nearly-linear time algorithm for linear programs with small treewidth: multiscale representation of robust central path. In Proceedings the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1784-1797, 2021.
[17] Alexander Fix, Thorsten Joachims, Sung Min Park, and Ramin Zabih. Structured learning of sum-of-submodullr higher order energy functions. In Proceedings of the IEEE International Conference on Computer Vision, pages 3104-3111, 2013.
[18] Roy Frostig, Rong Ge, Sham Kakade, and Aaron Sidford. Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization. International Conference Machine Learning, pages 2540-2548. PMLR, 2015.

---

[19] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algoritims and combina- torial optimization. Springer, 1988.
[20] Branko Grünbaum. Partitions of mass-distributions and of convex bodies by hyperplanes. Pacific Journal of Mathematics, 10(4):1257-1261, 1960.
[21] Osman Güler. On the self-concordance of the universal barrier function. SIAM Journal on Optimization, 7(2):295-303, 1997.
[22] Elad Hazan and Haipeng Luo. Variance-reduced and projection-fre stochastic optimization. In International Conference Machine Learning, pages 1263-1271. PMLR, 2016.
[23] He Jia, Aditi Laddha, Yin Tat Lee, and Santosh Vempala. Reducing isotropy and volume to kls: (n vb 2) volume algorithm. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 961-974, 2021.
[24] Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong. An improved cutting plane method for convex optimization, convex-concave games, and its applications. Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Compuring, pages 944 953, 2020.
[25] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013.
[26] Ravi Kannan, László Lovász, and Miklós Simonovits. Isoperimetric problems for convex bodies and localization lemma. Discrete & Computational Geometry, 13(3):541-559, 1995.
[27] Leonid G Khachiyan, Sergei Pavlovich Tarasov, and Erlikh. The method of inscribed ellipsoids. In Soviet Math. Dokl, volume 37, pages 226-230, 1988.
[28] Boas Klartag, On convex perturbations with a bounded isotropic constant. Geometric & Functional Analysis GAFA, 16(6); 2006.
[29] Pushmeet Kohli, Lubor Ladicky, and Philip H. S. Torr. Robust higher order potentials for enforcing label consistency. International Journal of Computer Vision, 82(3):302-33 2009.
[30] Alex Kulesza and Ben Taskar. Structured determinantal point processes. Advances in neural information processing systems, 23, 2010.
[31] Yin Tat Lee and Santosh S Vempala. Tutorial on the robust interior point method. arXiv preprint arXiv:2108.0 04734, 2021.
[32] Yin Tat Lee and Man-Chung Yue. Universal barrier is n-seff-concordant. Mathematics of Operations Research, 16(3):1129-111 12481148, 2021.
[33] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1049-1065, 2015.
[34] Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A universal catalyst for first-order optimiza- tion. Advances in neural information processing systems, 28, 2015.
[35] Mehrdad Mahdavi, Lijun Zhang, and Rong Jin. Mixed optimization for smooth functions. Advances in neural information processing systems, 26, 2013.
[36] Julien Mairal. Incremental ceteriiattoonmmiimiziitn optimization with application to large- scale machine learning. SIAM Journal on Optimization, 25(2):829-855, 2015.
[37] YE Nesterov and AS Nemirovskii. Self-concordant functions and polynomial time methods in convex programming, preprint, central economic & mathematical institute, ussr acad. Sci. Moscow, USSR, 1989.
[38] Yurii Nesterov and Arkadii Nemirovskii. Interior-point polynomial algorithms in convex programming. SIAM, 1994.
12

---

[39] Yurii E Nesterov. A method for solving the convex programming problem with convergence rate (L/kk²) In Dokl. akad. nauk Sssr, volume 269, pages 543-547, 1983.
[40] Yurii E. Nesterov. Introductory Lectures on Convex Optimization A Basic Course, volume 87 of Applied Optimization. Springer, 2004. doi: 10.1007/978-1-440 14419-883-9-
[41] Yurii E. Nesterov and Arkadii Nemirovskii. Interior-point polynomial algorithms in convex programming, volume 13 of Siam studies in applied mathematics. SIAM, 1994. ISBN 978-0-89871-319-0. doi: 011113//177811119777777 URL https://doi.. org/10 1r1//1.1137/11. 9781611970791.
[42] Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. Advances in neural information processing systems, 24, 2011.
[43] James Renegar. A mathematical view of interior-pone methods in convex optimization. SIAM, 2001.
[44] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
[45]
R Tyrrell Rockafellar. Conver Analysis, volume 36. Princeton University Press, 1970.
[46] Nicolas Roux, Mark Schmidt, and Francis Bach, stochastic gradient method with an exponen- tial convergence rate for finite training sets. Advances in neural information processing systems, 25, 2012.
[47] Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1):83-112 2017.
[48] Shai Shalev-Shwartz and Tong Zhang. Accelerated mini-batch stochastic dual coordinate ascent. Advances in Neural Information Processing Systems, 26, 2013.
[49] Shai Shalev-Shwartz and Tong Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, 14(2), 2013.
[50] Peter Stobbe and Andreas Krause. Efficient minimization of decomposable submodular func- tions. Advances in Neural Information Processing Systems, 23, 2010.
[51] Pravin M Vaidya. A new algorithm for minimizing convex functions over convex sets. In 30th Annual Symposium on Foundations of Computer Science, pages 338-343, 1989.
[52] Nate Veldt, Austin R Benson, and Jon Kleinberg. Minimizing localized ratio cut objectives in hypergraphs. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1708-1718, 2020.
[53] Sara Vicente, Vladimir Kolmogorov, and Carsten Rother. Joint optimization of segmentation and appearance models. In 2009 IEEE 12th international conference on computer vision, pages 755-762. IEEE, 2009.
[54] Blake E Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. Advances in neural information processing systems, 29, 2016.
[55] Tong Zhang. Solving large scale linear prediction problems using stochastic gradient descent algorithms. In Proceedings of the twenty-fist international conference on Machine learning, page 116, 2004.
[56] Yuchen Zhang and Xiao Lin. Stochastie primal-dual coordinate method for regularized empirical risk minimization. In International Conference Machine Learning, pages 353-361. PMLR. 2015.
[57] Manru Zong, Yin Tat Lee, and Man Chung Yue. Short-step methods are not strongly polynomial- time, arXiv preprint 22X::22001.0266. 2022.
Man-Chung
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 1.1.1
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Due to the theoretical nature of our work, we do foresee any immediate potential negative societal impacts of it.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes] We state all our assumptions in Problem 1.
(b) Did you include complete proofs of all theoretical results? [Yes] All our complete proofs are the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "wQefSZyY8KR", "reviewer": "Reviewer_wH1T", "summary": "This work developed a new algorithm with near linear gradient oracle complexity (in terms of total effective dimension) for finite-sum non-smooth convex optimization, which appears to be the first work of achieving this goal.", "questions": "See strengths and weaknesses.", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The proposed algorithm is based on a novel combination of cutting-plane methods and interior-point methods, which is technically non-trivial. The method achieves near linear gradient oracle complexity in terms of total effective dimension, which matches the theoretical lower bound. The result drastically improves upon the complexity of directly applying cutting-plane method when the gradients are sparse. Overall the paper is well written. \n\nWeaknesses:\n\n- It would be great if the authors can provide a discussion on prior works that deal with non-smooth empirical risk minimization problem (i.e., ERM with a non-smooth regularizer that admits an efficiently computable proximal operator), which helps understanding the positioning of this work.\n\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "oK9ul88jeeG", "reviewer": "Reviewer_TejV", "summary": "In this work, the authors proposed a weakly-polynomial algorithm to minimize the finite-sum objective function, which is possibly non-smooth. The complexity of the proposed algorithm improves that of the cutting-plane methods, under the assumption that each component f_i only depends on a small subset of the components of x. The algorithm is a combination of the interior-point method and the cutting-plane method.", "questions": "Major:\n(1) The presentation of the paper should be improved. For example, the discussion in lns.140-149 is based on definitions/results in Section 3. The readers have to complete reading the whole paper to understand the intuition that the authors wanted to convey here. This will make this discussion less useful in \"introducing\" the readers to the contributions of this paper. It might be helpful to explain what are inequalities (3.3) and (3.4).\n\n(2) In addition, it is a little confusing why the complexity of the proposed algorithm has dependence on m rather than nd. It seems to me that the dependence on m suddenly appeared on ln.325. Hence, it would be better to provide an intuition on the dependence on m.\n\n\nMinor: \n(1) It would be better to mention that in the SFM problem, one can utilize the Lovasz extension to compute a sub-gradient in O(d) steps. Otherwise, readers that didn't read the appendix will be confused on the relation between the evaluation oracle and the sub-gradient oracle.\n\n(2) Ln.94: it would be better to clarify the definition of the \"polynomial factor\". Namely, is this factor a polynomial of d_i and epsilon, or something else?\n\n(3) Ln.102: since the AGD algorithm updates one coordinate in each iteration, I wonder if the complexity is proportional to d? Also, I do not understand why AGD can only update one coordinate in each iteration, and it seems that the complexity Omega(n^2) does not match the complexity in Table 1? It would be better to provide more details to this discussion.\n\n(4) Ln.106: it would be better to use \"sub-gradient\" instead of \"gradient\" in the discussion of CPM, since it does not require the smoothness condition.\n\n(5) Ln.127: K_i is not defined.\n\n(6) Ln.138: please unify the usage of \"sub-gradient\" and \"subgradient\". Also, \"a separation oracle K_i\" -> \"a separation oracle of K_i\".\n\n(7) What are c, A and b in problems (1.4) and (3.1)?\n\n(8) Lns.140-149: it seems that the case when inequality (3.4) is violated is not discussed.\n\n(9) Ln.175: y should be boldface letter.\n\n(10) Ln.200: I wonder if the convex set K_i is defined by the epigraph of f_i? If so, please clarify the meaning of \"does not have a closed-form expression\". If not, please provide a more explicit definition of K_i.\n\n(11) Ln.224: does the Newton step refer to Ln.23 of Algorithm 1?\n\n(12) For the discussion around Prop.2, I wonder what is the difference between the claim here, and the classic \"volume reduction\" results in CPM algorithms?", "limitations": "See my comments in the \"questions\" section.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work provides a novel algorithm for the non-smooth finite-sum optimization problem. In addition, the complexity is improved in certain cases. Although I haven't read the appendix, the intuitions on the technical proofs seem reasonable to me. Therefore, I think this work will be interesting to audiences in optimization and machine learning.\n\nOn the other side, given the technical complexities of this work and the page limit of the conference, it is a little hard to present the results clearly. With that said, I still suggest the authors try to revise the presentation and organization of this work. In addition, it would be better if numerical results can be provided.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "lieCAIImCM3", "reviewer": "Reviewer_5YUr", "summary": "This paper investigates the finite sum minimization problem where each function depends only on a subset of coordinates. The work combines cutting plane and interior point methods and achieves a better complexity in gradient oracles. As always, however, there is a catch.\n", "questions": "Some minor comments: \n\n1. While we start with a problem (1.1) which is unbounded, we don't actually use it. The reformulation we use already assumes compactness. I think (1.1) only confuses. Also it uses $\\theta$, while later we switch to $x$ variables, and we actually never show how this reformulation to (1.4) happens.\n\n2. Table 1: In (1.1) we didn't assume strong convexity, while some methods in the table do. Thus, it is not clear what the authors want to convey. Also, what is the purpose of the last column? Subgradient methods handle this problem under non-smoothness.\n\n3. line 50: It is not clear what \"long chain of variable dependencies\" is.\n\n4. line 126-136: I suggest to be more instructive here. How exactly do you transform (1.1) into that form? What is the role of linear constraints $Ax=b$?\n\n5. line 144-145: Inequalities (3.3) and (3.4) at this moment are not yet established, thus the explanation looks rather void.\n\n6. Th. 2.3: We don't explain what is centroid here, however we provide a full line of text for the elementary definition of the halfspace.\n\n7. line 192: No need to repeate notation of the polar set: it was defined just a few paragraphs above.\n\n", "limitations": "-", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "While the paper's contribution and motivation are definitely sound and interesting, especially from a mathematical point of view, I don't see its relevance to the NeurIPS community. For instance, the algorithm relies on the entropic barrier which is not implementable in general. Thus, the proposed complexity, in my opinion, is rather theoretical, with no hope to be practical. \n\nThis contribution also requires significant resources for review and hence for appreciation of the technique and with review workload we have this has been nearly impossible. Anyway, I think a venue with more focus on complexity would be a better fit for this work. \n", "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": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "e5hK-zuCOH_v", "reviewer": "Reviewer_Q9he", "summary": "This paper studies a class of decomposable convex optimization problem. An algorithm with optimal query complexity is proposed. In addition, the authors also improve the evaluation oracle complexity for decomposable submodular minimization.", "questions": "What is the definition of $\\mathcal{K}_i$ that appeared in Section 1.2 and 1.3?", "limitations": "This is a theory paper and I believe there is no potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This paper makes solid contribution to decomposable convex optimization problem with possibly non-smooth objective. The authors propose new algorithm for this problem with optimal query complexity. The proof technique in this paper is novel.\n\nWeaknesses: The organization and presentation of this paper needs to be improved. \n1. I believe the main algorithm should be presented more clearly and explicitly in the main text, namely one should be able to implement Algorithm 1 after reading Section 3. Currently Section 3.1 seems like a mixture of implementing details and algorithmic intuitions, but due to space limitation I think the authors are not able to present either of them clearly. For example, how to set the initialization K_in, K_out and x_initial? The readers are referred to Appendix C.1 and C.2, where they might only find theorems and proofs instead of implementing details. What is the expression of A, b and c using the quantities already introduced in the main text? Can each step in Algorithm 1 be computed efficiently?\n2. I think at least some part of Section 2 is not necessary for the main text, which can be moved to the appendix and save space for presenting and explaining algorithmic details.\n3. I don't see a reason why the authors only present informal theorem (Theorem 1.2) in the main text and defer the formal theorem to the appendix. It seems to me that the formal theorem is not too complicated.\n\n---------------After rebuttal----------------------\n\nI would like to thank the authors for their response. Given that all my comments and authors' response leads to revision in the next version of the paper, I decide to keep my score and leaning to an accept.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept