Unifying Width-Reduced Methods for Quasi-Self-Concordant Optimization
Year: 2021

Abstract:
We provide several algorithms for constrained optimization of a large class of convex problems, including softmax, `p regression, and logistic regression. Central to our approach is the notion of width reduction, a technique which has proven immensely useful in the context of maximum flow [Christiano et al., STOC’11] and, more recently, `p regression [Adil et al., SODA’19], in terms of improving the iteration complexity from O(m1/2) to Õ(m1/3), where m is the number of rows of the design matrix, and where each iteration amounts to a linear system solve. However, a considerable drawback is that these methods require both problemspecific potentials and individually tailored analyses. As our main contribution, we initiate a new direction of study by presenting the first unified approach to achieving m1/3-type rates. Notably, our method goes beyond these previously considered problems to more broadly capture quasi-selfconcordant losses, a class which has recently generated much interest and includes the well-studied problem of logistic regression, among others. In order to do so, we develop a unified width reduction method for carefully handling these losses based on a more general set of potentials. Additionally, we directly achieve m1/3type rates in the constrained setting without the need for any explicit acceleration schemes, thus naturally complementing recent work based on a ball-oracle approach [Carmon et al., NeurIPS’20].

heading: 1 Introduction
text: We study a class of constrained optimization problems of the following form:
min Ax=b
X
i
f (Px )i
(1)
for convex f : R! R, where A 2 Rd⇥n, b 2 Rd,P 2 Rm⇥n, with d  n  m. Specifically, we are interested in the case where f satisfies a certain higher-order smoothness-like condition known as M -quasi-self-concordance (q.s.c.), i.e., |f 000(x )|  Mf 00(x ) for all x 2 R. Several problems of significant interest in machine learning and numerical methods meet this condition, including logistic regression [Bac10, KSJ18], as well as softmax (often used to approximate `1 regression) [Nes05, CKM+11, EV19, Bul20] and (regularized) `p regression [BCLL18, AKPS19].
A very useful optimization technique, first introduced by [CKM+11] for faster approximate maximum flow and later by [CMMP13] for regression, is that of width reduction, whereby they used it to improve the iteration complexity dependence on m, the number of rows of the design matrix from O(m1/2) to Õ(m1/3), and where each iteration requires a linear system solve. Later work by [AKPS19] for high-accuracy `p regression, building on an O(m1/2)-iteration result from [BCLL18], again showed
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
how width reduction could lead to improved Õ(m1/3)-iteration algorithms. As a drawback, however, these approaches rely on potential methods and analyses specifically tailored to each problem.
Building on these results, we present the first unified approach to achieving m1/3-type rates, at the heart of which lies a more general width reduction scheme. Notably, our method goes beyond these previously considered problems to capture quasi-self-concordant losses, thereby further including well-studied problems such as logistic regression, among others. By doing so, we directly achieve m
1/3-type rates in the constrained setting without relying on explicit acceleration schemes [MS13], thus complementing recent work based on a ball-oracle approach [CJJ+20]. We additionally note that, given the ways in which our results achieve improvements similar to those of [CJJ+20], we believe our work hints at a deeper, though to our knowledge not yet fully understood, connection between the techniques of width reduction and Monteiro-Svaiter acceleration.

heading: 1.1 Main Results and Applications
text: We first present in Section 3 a width-reduced method for obtaining a crude approximation to (1) for quasi-self-concordant f . At a high level, our algorithm returns an approximate solution x̃ that both satisfies the linear constraints and is bounded in `1-norm by O(R), where R is a bound on the norm of the optimal solution. Following from Theorem 3.3, the result below shows how, for the problem of minimizing softmax (parameterized by ⌫ > 0), i.e., smax⌫(Px ) = ⌫ log ⇣P i e (Px)i ⌫ ⌘ , we can bound
the norm of the solution by (1 + ⌫)R. Theorem 1.1. Let x ? denote the optimum of minAx=b smax⌫(Px ). Algorithm 1 when applied to the function f (Px ) = P i e (Px)i ⌫ with ✏ = ⌫, returns ex such that Aex = b , and
smax⌫(Pex )  (1 + eO(⌫))smax⌫(Px ?),
in at most eO(m1/3⌫ 5/3) calls to a linear system solver.
As a consequence of Theorem 1.1 when taking ⌫ = ⌦ ⇣ ✏/ logO(1)(m) ⌘ , we have by Theorem 5.2 a
(1 + ✏) approximate solution to the problem of `1 regression with Õ(m1/3✏ 5/3) calls to a linear system solver.
Further, we show the following result which can use the approximate solution returned by Theorem 1.1 as an initial point for achieving a high-accuracy solution. We also present in Appendix A a natural extension of our results to minimizing general-self-concordant (g.s.c.) functions.
Theorem 1.2. For M -q.s.c. f , ✏ > 0, and x (0) such that Ax (0) = b and kx (0)k1  R, Algorithm 2
finds ex such that Aex = b and f (ex )  ✏+ f (x ?) in eO MRm 1/3 log(MR) log
✓ f (x (0)) f (x?)
✏
◆!
calls to a linear system solver.
Resulting from the theorem above, as detailed in Section 5, are guarantees given by Theorems 5.4 and 5.5 which establish convergence rates of eO(p2µ 1/(p 2)m1/3R) and eO(m1/3R), respectively, for µ-regularized `p regression and logistic regression. We emphasize that the latter is, to our knowledge, the first such use of width reduction for directly solving constrained logistic regression problems.

heading: 1.2 Related Works
text: Quasi-self-concordance and higher-order smoothness. [Bac10] showed how to analyze Newton’s method for quasi-self-concordant functions, with an emphasis on its application to logistic regression. Later, notions of local, or Hessian, stability which follow from quasi-self-concordance gave rise to methods with better dependence on various conditioning parameters along with a linear rate of convergence [KSJ18, MFBR19, CJJ+20]. In the work by [KSJ18], the authors show how a trust-region-based Newton method [NW06] achieves linear convergence for locally stable functions without requiring, e.g., strong convexity. Meanwhile, after noting that quasi-self-concordance implies Hessian stability, [CJJ+20] further improve the dependence on the distance to the optimum by leveraging Monteiro-Svaiter acceleration [MS13], which has proven useful in the context of near-optimal methods for higher-order acceleration [ASS19, GDG+19]. However, in general these methods, which
assume higher-order smoothness, require access to an oracle which minimizes a higher-order Taylor expansion model, though in some cases this may be relaxed to requiring linear system solves [Bul20].
Width reduction and `p regression. The notion of width is common in the multiplicative weights literature [PST95, Fle00, GK07]. Most of these algorithms repeatedly solve a certain subproblem, and “width” is defined as an upper bound on the `1-norm of the solution to these subproblems. The runtime of such algorithms depends linearly on the width, and since this quantity can have a large value, several approaches have been proposed to reduce the width.
The technique of width-reduction first came to prominence in seminal work by [CKM+11] for achieving faster approximate maximum flow, being the first to achieve an improved m1/3 dependence. At a high level, the idea behind the approach is to solve a sequence of weighted `2-minimizing flow subproblems, whereby at each iteration one of two cases occurs: either the proposed step is added to the current solution (a "flow" step) along with the weights, or else there exist some set of coordinates that exceed a certain threshold, and so their weights are updated accordingly (a "width reduction" step). Several works have since adapted this approach to regression problems [CMMP13, AKPS19, EV19, ABKS21] and matrix scaling [AZLOW17]. In particular, when comparing with [EV19], we note that the update steps for the weights are different from our algorithm. We also note that the number of width reduction steps in our algorithm are restricted by ✏ 2/3 iterations, which is similar to [EV19], but our algorithm requires ✏ 5/3 flow steps.
In addition to their importance in machine learning, regression methods capture several fundamental problems in scientific computing and signal processing. A recent line of work initiated by [BCLL18] showed how to attain high-accuracy solutions for `p regression using Op(m1/2 1/p) linear system solves, thus going beyond what is achievable via self-concordance. Building on this work, [AKPS19] showed how width reduction could be applied to this setting to achieve, as in the case of approximate maximum flow [CKM+11], a similar improvement from Op(m1/2) to Op(m1/3) (for p ! 1). Further developments by [KPSW19, AS20] for graph problems showed almost-linear time solutions for `p regression for p ⇡ p log(n) which have since been a critical part of recent advances in high-accuracy maximum flow on unit-capacity graphs [LS20, KLS20].
Accelerated methods. Recent developments by [CJJ+20] have shown several advantages that arise in the case of unconstrained minimization for smooth, quasi-self-concordant problems. By considering a certain ball oracle method (whereby each call to the oracle returns the minimizer of the function inside an `2 ball of radius r), [CJJ+20] implement an accelerated scheme which returns a solution to the unconstrained smooth convex minimization problem in (R/r)2/3 calls to the oracle, where R is the initial `2-norm distance to the optimum, and they further show a matching lower bound under this oracle model. We note here that while our method obtains rates in terms of the `1-norm of the optimum rather than the `2-norm, in the worst case, we can have kx ?k2 = p mkx ?k1, which results in both rates being essentially the same.
While the approach of [CJJ+20] transfers its difficulty to implementing the oracle, a key insight from their work involves showing this can be done efficiently for smooth quasi-self-concordant functions when r is sufficiently small, where the allowed size depends on the quasi-self-concordance parameter. One limitation to their results is that they apply directly to unconstrained optimization problems and require the function to be smooth, and so we complement these results in the quasi-self-concordant setting by establishing comparable rates for directly optimizing a large class of constrained convex problems without requiring smoothness of the function.

heading: 1.3 Outline of the Paper
text: After establishing the potential functions at the heart of our width reduction techniques, we present in Section 3 our oracle for roughly approximating a solution to problem (1). We then show in Section 4 how we may attain a high-accuracy solution by using the crude approximation as a starting point. Here, the key idea is to considering a sequence of optimization problems inside `1 balls of manageable size, similar to [CMTV17, CJJ+20]. As in the case of the crude oracle, our primary advantage comes from carefully handling a pair of coupled potentials which are amenable to the large class of quasi-self-concordant problems, and in Section 5 we further show how our results may be applied to several problems of interest, including logistic and `p regression.

heading: 2 Preliminaries
text: Notation: We use boldface lowercase letters to denote vectors or functions and boldface uppercase letters for matrices. Scalars are non-bold letters. Our functions are univariate, and we overload function notation to act on a vector coordinate-wise, i.e. f (x ) = P i f (x i). The notation x y for vectors refers to entry-wise inequality. Refer to the algorithm boxes for definitions of certain algorithm specific parameters that appear in lemma and theorem statements.

heading: 2.1 Quasi-Self-Concordance
text: Definition 2.1 (g.s.c. and q.s.c.). Let f : R! R be a thrice differentiable function with continuous third derivative, and let ⌫ > 0 and M > 0. We say that f is (M, ⌫)-general-self-concordant (g.s.c.) if 8x, |f 000(x)| Mf 00(x) ⌫2 . When ⌫ = 2, we have the following condition: 8x, |f 000(x)| Mf 00(x), and we call such functions M -quasi-self-concordant (q.s.c.).

heading: 2.2 Problem
text: Recall that we are solving the following problem:
min Ax=b
X
i
f (Px )i ,
where A 2 Rd⇥n, b 2 Rd,P 2 Rm⇥n, d  n, and m n, and such that f is convex, M -q.s.c. and, for w w0 0, f 00(w i) is monotonic 8i. We can ignore the case when f 00 is constant since that corresponds to a quadratic problem which we know how to solve directly via linear system solves.
Assumptions on the Optimum x ?
We assume that R 2 R>0 is such that the optimum x ? def = argminAx=b f (Px ) satisfies
kPx ?k1  R. (2)
We now define the potentials that we track in the algorithm.

heading: 2.3 Potentials
text: Definition 2.2 (Dual Potential). For a weights vector w 2 Rm 0, we define a potential
(w) = X
i
(w i) = X
i
f 00(w i).
We also define the following corresponding potential, which gives rise to the linear regression problem that we will need to solve at each step of our algorithm. Definition 2.3 (Resistances and Corresponding Potential). For a weights vector w 2 Rm 0 and ✏ > 0, define resistances r 2 Rm 0 and a corresponding potential as,
r i = 1
R2
✓ f 00(w i) + ✏ (w)
m
◆ ,
(r) = min A =b
X
i
r i(P ) 2 i .
We have the following relation between our two potentials and . Lemma 2.4. For ✏ > 0, resistances r (Definition 2.3), with corresponding weights w , we have
(r)  (1 + ✏) (w). In addition, letting kPkmin = minAx=b kPxk2 and kAk denote the operator norm of A, we have
(r) ✏ (w) mR2 kPk2minkbk22 kAk2 def = (w)L.

heading: 3 Algorithm and Analysis for a Crude Solution for Q.S.C. Functions
text: In this section, we give an algorithm for solving Problem (1) to a crude approximation; namely, we return a solution ex such that Aex = b , i.e., it satisfies the subspace constraints, and kPexk1 is bounded. We will later see in our applications how this translates into a constant or polynomial approximation guarantee to the function value for some functions. In the next section we will see how we can use the guarantees of the solution returned as a starting solution and boost it to an ✏ approximate solution.
Our algorithm is based on combining a multiplicative weight update (MWU) scheme with width reduction. Though such algorithms have so far only been used for `p-regression, p = 1 or p 2 [2,1], here we are able to extend the analysis to q.s.c. functions, while also providing a unified analysis for the known cases of `p-regression (refer to Section 5 to see how we apply this algorithm to these instances). We note that we can extend this analysis to other general-self-concordant functions, and we have deferred these cases to the appendix.

heading: 3.1 Algorithm and Analysis
text: We describe our width-reduced multiplicative weight update method in Algorithm 1. We note that the width of |P | is being reduced, though the weight updates are not entirely multiplicative. For a width step it is multiplicative in f 00(w) (lines 14-18), but for a flow step (line 11) we perform a purely additive update directly on the weights.
Our proof relies on tracking two potentials, (Definition 2.3) and (Definition 2.2) that depend on the weights. We first show how these potentials change with weight updates corresponding to a flow step and a width reduction step in the algorithm. We next show that if our algorithm runs for at most K = eO(m1/3) width reduction steps, then after T = eO(m1/3) flow steps we can bound . Further, using the relation between and (Lemma 2.4) and appropriately chosen parameters, we show that we cannot have more than K width reduction steps. The key part of the analysis lies in the growth of with respect to both flow and width steps.
Algorithm 1 Width-Reduced Algorithm for M -q.s.c. Functions 1: procedure QSC-MWU(A, b,P ,M,R, ✏) 2: x (0,0) = 0,w (0,0) = w0 ( 0(w) monotonic for w w0, (w0) > 0) 3: ⌧ e⇥ ⇣ m 1/3 ✏ 2/3 ⌘
4: ↵ e⇥ ⇣ m 1/3 M 1 ✏ 2/3 ⌘
5: t = 0, k = 0, T = ↵ 1M 1✏ 1 = e⇥(m1/3✏ 5/3) 6: while t  T do 7: r (t,k)
i 1 R2
✓ f 00(w (t,k)
i ) + ✏ (w (t,k)) m
◆ . Resistances
8: e argminA =b P i r i(P )2i . Oracle 9: if P e
1  R⌧ then . Flow Step
10: x (t+1,k) x (t,k) + e 11: w (t+1,k) w (t,k) + ✏↵
R |P e |
12: t t+ 1 13: else 14: for Indices i such that |P e |i R⌧ do . Width Reduction 15: if f 00 is non-decreasing in w then1 16: w (t,k+1) is such that r (t,k+1) i (1 + ✏)r (t,k) i 17: else 18: w (t,k+1) is such that r (t,k+1)
i 11+✏r (t,k) i

heading: 19: k k + 1
text: 20: return x (T,k)/T
1We will see later how such weight/resistance changes can be realized for some special cases.
Changes in and
Here we show how the potentials and change with flow and width reduction steps, and we defer the proofs to the appendix. Lemma 3.1. Let be as defined in 2.3. After t flow steps and k width reduction steps, we have,
(r (t,k)) (r (0,0)) 1 +
✏ 2 ⌧ 2
(1 + ✏)2m
!k if f 00 non-decreasing in w ,
(r (t,k))  (r (0,0)) 1 ✏
2 ⌧ 2
2(1 + ✏)2m
!k if f 00 non-increasing in w .
Lemma 3.2. Suppose f is M -q.s.c. Let ↵ and ⌧ be such that ↵⌧ M 1. After t flow steps and k width reduction steps, our potential satisfies
(w (t,k))  ⇣ 1 + ✏(1 + ✏)2↵M ⌘t⇣ 1 + ✏(1 + ✏)⌧ 1 ⌘k (w0) if f 00 non-decreasing in w , (w (t,k)) ⇣ 1 ✏(1 + ✏)2↵M ⌘t⇣ 1 ✏(1 + ✏)⌧ 1 ⌘k (w0) if f 00 non-increasing in w .
Runtime Bound
We now establish the final rate of convergence for Algorithm 1.
Theorem 3.3. Let ✏ > 0, f be M -q.s.c. After T  ↵ 1 M✏ = e⇥(m1/3✏ 5/3) flow steps and K  ⌧ = e⇥(m1/3✏ 2/3) width reduction steps, Algorithm 1 returns ex such that Aex = b , kPexk1  RMkw (T,K)k1, where w (T,K) is the final weights vector that satisfies:
(w (T,K))  (w0)e1+4✏ if f 00 is non-decreasing in w , (w (T,K)) (w0)e (1+4✏) if f 00 is non-increasing in w .
Proof. We show the case when f 00 is a non-decreasing function. The other case follows similarly. We set,
⌧ e⇥ ⇣ m 1/3 ✏ 2/3 ⌘ ↵ e⇥ ⇣ m 1/3 M 1 ✏ 2/3 ⌘ .
After T = ↵ 1
M✏ flow steps and K = ⌧ width reduction steps, from Lemma 3.2, we have,
(w (T,K))  ⇣ 1 + ✏(1 + ✏)2↵M ⌘T⇣ 1 + ✏(1 + ✏)⌧ 1 ⌘K (w0)
 (w0)e✏(1+✏) 2 ↵MT+✏(1+✏)⌧ 1K  (w0)e(1+4✏).
We now show we cannot have more width steps. Throughout the algorithm, we have (w (t,k))  (w0)e1+4✏. From Lemma 2.4 we always have (r (0,0)) (w0)L and (r (T,K))  (1 + ✏) (w (T,K))  (1 + ✏)e1+4✏ (w0). Thus, from Lemma 3.1, we must have,
(1 + ✏)e1+4✏ (w0) L (w0) 1 +
✏ 2 ⌧ 2
(1 + ✏)2m
!K ,
From the definition of ⌧ , we note that K has to be less than ⌧ for the above bound to be satisfied. Next, let e (t) denote the solution of our oracle at iteration t of the flow step. From the x and w update in the algorithm,
|Pex | =
X
t
P e (t) ✏↵M 
✏↵
R
X
t
P e (t) RM  w (T,K)RM.
This concludes our proof.

heading: 4 Boosting to a High-Accuracy Solution for Q.S.C. Functions
text: In this section, we give a width-reduced multiplicative weights update algorithm that, given a starting solution x (0) satisfying kx (0)k1  R and Ax (0) = b , finds ex such that Aex = b and f (ex )  (1 + ✏)f (x ?) for any q.s.c. function f . We would mention here that for the algorithms in this section, it is key that we have a starting solution that satisfies our subspace constraints and has `1-norm bounded by R. Thus, the algorithms here may be of independent interest if such a starting solution is available. We can otherwise use Algorithm 1 with ✏ = 1 to obtain such a solution.
For any x , we define a residual problem, and we show how it is sufficient to solve the residual problem approximately log(✏ 1) times to obtain our high-accuracy solution. Similar approaches have been applied to specific functions such as softmax [AZLOW17] and `p-regression [AKPS19]. We unify these approaches and give a version that works for any q.s.c. function.
We further note that, in the spirit of [AZLOW17], our residual problem is to optimize a simple quadratic objective inside an `1 box. The difficulty lies in solving such `1 box constraints fast. We use a binary search followed by a width-reduced multiplicative weights routine analogous to [CKM+11] to solve our residual problem. Definition 4.1 (Residual Problem). We define the residual objective at any x satisfying kPxk1  R as res( ) = rf (x )>P e 1(P )>r2f (x )P , and the residual problem as
max res( )
s.t. A = 0, and kP zk1  1
2M .
(3)
Here, z is a vector that depends on x , and is defined as
z i =
8 ><
>:
12M +R+ (Px )i 2 [ 12M , 0)], if (Px )i 1 2M < R R+ (Px )i + 12M 2 (0, 12M ], if (Px )i + 1 2M > R
0, otherwise.
We note that any solution satisfying the above box constraint satisfies kP k1  M 1 and Px e 2P 1  R.
Lemma 4.2. [Iterative Refinement] Let f be M -q.s.c. and e (t) a -approximate solution to the residual problem at x (t) (Problem (3)). Starting from x (0) such that Ax (0) = b , kx (0)k1  R, and
iterating as x (t+1) = x (t) e 2 e (t), after at most O MR log
✓ f (x (0)) f (x?)
✏
◆! iterations we
get x such that Ax = b and f (x )  f (x ?) + ✏.

heading: 4.1 Approximately Solving the Residual Problem
text: Binary Search
Lemma 4.3. Let ⌫ be such that f (x (t)) f (x ?) 2 (⌫/2, ⌫] and ? denote the optimum of the residual problem at x (t). Then, res( ?) 2 ⌫ 8MR , e 2 ⌫ ⇤ .
From the above lemma we may do a binary search in the range
⌫ 8MR , e 2 ⌫ ⇤ . Let us start with the
assumption that the residual problem has a solution between (⇣/2, ⇣]. Lemma 4.4. Let ⇣ be such that res( ?) 2 (⇣/2, ⇣] and ? the optimum of the residual problem. Then, (P ?)>r2f (x )P ?  e · ⇣.
Using Width Reduction
We will show that Algorithm 3 returns such that kP zk1  12M and res( ) 1 400⇣.
Algorithm 2 Boosting to ✏-approximation 1: procedure QSC-MIN((A, b,P ,x 0,M, ✏) such that Ax 0 = b , kx 0 x ?k1  2R) 2: x (0) = x 0, ⌧ m1/3,↵ m 1/3 3: for i  O(MR log ✏ 1) do 4: for ⌫ 2 ✏, f (x ) ⇤ do . Decrease ⌫ by 2 in each iteration
5: for ⇣ 2
⌫ 8MR , e 2 ⌫ ⇤
do . Decrease ⇣ by 2 in each iteration 6: y⇣,⌫ MWU(A,P ,x (i),M, ⇣) 7: x (i+1) x (i) e 2 argminy⇣,⌫ f (x e 2y⇣,⌫)
Algorithm 3 1: procedure MWU(A,P ,x ,M, ⇣) 2: y (0) = 0,w (0) = ⇣
m
3: t = 0 4: A0 = h A>,P>rf (x ) i> , b = [0, ⇣2 ] 5: while kwk1  10⇣ do 6: e argminA0 =b0 P j f 00(x j)(P )2j + 4M 2 P j ✓ w (t) j + kw (t)k1 m ◆ (P z )2 j
7: if 2M P e z
1  ⌧ then . Flow Step
8: y (t+1) y (t) + e 9: w (t+1) w (t) ⇣ 1 + 12↵M |P e z | ⌘
10: else 11: for Indices i such that 2M |P e z |i ⌧ do 12: w (t+1)
i 2w (t) i . Width Step
13: t t+ 1 14: return y (t)
100t
Lemma 4.5. Let ⇣ be such that res( ?) 2 (⇣/2, ⇣]. Algorithm 3 returns y such that Ay = 0, kPy zk1  12M and res(y) 1 400res( ?) in O(m1/3) calls to a linear system solver.
We now state the main result of the section which follows directly from Lemmas 4.2, 4.3 and 4.5.
Theorem 4.6. For ✏ > 0, M -q.s.c. function f and, x (0) such that Ax (0) = b , kx (0)k1  R, Algorithm 2 finds ex such that Aex = b and f (ex ) f (x ?)  ✏ in
eO MRm 1/3 log(MR) log
✓ f (x (0)) f (x?)
✏
◆! calls to a linear system solver.

heading: 5 Applications
text: We now show how our methods may be applied to various quasi-self-concordant functions.
5.1 Sum of Exponentials, Softmax and `1-regression
We recall the softmax function smax⌫(Px ) = ⌫ log ⇣P
i e
(Px)i ⌫ ⌘ , which we may note is 1/⌫-q.s.c.
We start by assuming that at the optimum, for R ⌦ (logm) 1 , smax⌫(Px ?)  R.
We apply Algorithm 1 to P
i e
(Px)i ⌫ , which is also 1/⌫-q.s.c. We can use the following weight update
step for the width reduction step: w (t,k+1) i
w (t,k) i + ⌫ log(1 + ✏).
Theorem 5.1. Let x ? denote the optimum of minAx=b smax⌫(Px ). Algorithm 1, when applied to the function f (Px ) = P i e (Px)i ⌫ , returns ex such that Aex = b , and
smaxt(Pex )  (1 + eO(⌫))smax⌫(Px ?),
in at most eO(m1/3⌫ 5/3) calls to a linear system solver.
Proof. We know that smax⌫(Pex )  kPexk1 + ⌫ logm. From Lemma 3.3, we have that ex is obtained in at most eO(m1/3⌫ 5/3) calls to a linear system solver satisfying Aex = b . Further, we also have, kPexk1  MRkw (T,K)k1 = R kw (T,K)k1 ⌫ . We will now bound kw (T,K)k1 ⌫ . We note that (w (T,K))  (w0)e1+4⌫ . For w0 = 0,
(w (T,K)) = 1
⌫2
X
i
e
w (T,K) i ⌫ = (w0) X
i
e
w (T,K) i
⌫  (w0)e1+4⌫ .
Therefore, we must have w (T,K)  (1 + 4⌫)⌫. Our bound is
smax⌫(Pex )  (1 + 4⌫)R+ ⌫ logm  ⇣ 1 + eO(⌫) ⌘ R,
for R ⌦(1/ logm). We can now do a binary search on R as follows to obtain
smax⌫(Pex )  (1 + eO(⌫))smax⌫(Px ?).
Binary search on R: Let R0 denote the value kPx ?k1 = R0. Now, for any R R0, we attain an ex which has an objective value at most R(1 + 4⌫). For any R < R0, as long as R is such that the plane Ax = b has at least one point with infinity norm at most R, we will get a feasible solution to our problem. However, the objective value guarantee of R(1 + 4⌫) may not hold. Since the optimum is R0, the solution returned in such cases must give an objective value larger than R0. We can thus do a binary search on R and reach O(⌫) close to the value R0. This will require running our algorithm O log(R0⌫ 1) times. In the end we can return the x which gives the smallest objective values among all these runs.
Theorem 5.2. Let x ? denote the optimum of the `1-regression problem, minAx=b kPxk1. Algorithm 1 when applied to the function f (Px ) = P i ⇣ e (Px)i ⌫ + e (Px)i ⌫ ⌘ for ⌫ = ⌦ ⇣ ✏ logm ⌘ , returns ex such that Aex = b and kPexk1  (1 + ✏)kPx ?k1,
in at most eO(m1/3✏ 5/3) calls to a linear system solve.
Theorem 5.3. For > 0, let x be the solution returned by Algorithm 1 (with ✏ = 1) applied to f (Px ) = P i e (Px)i ⌫ . Now, Algorithm 2 with starting solution x (0) = x , applied to f finds ex such that Aex = b and P
i e
(Pex)i ⌫  (1 + ) P i e (Px?)i ⌫ in at most O ⇣ m 1/3 R 2 ⌫ 2 log m ⌘ calls to a
linear system solver.
5.2 p-Norm Regression
We will solve, minAx=b f (Px ) = kPxkpp + µkPxk22, for p 3 which is pµ 1/(p 2)-q.s.c. w.r.t. its argument. We first apply Algorithm 1 to this function and use the returned solution as the starting point of Algorithm 2. We can use the following weight update step for the width reduction step: w (t,k+1)
i (1 + ✏)1/(p 2)w (t,k) i .
Theorem 5.4. For > 0 and p 3, let x be the solution returned by Algorithm 1 (with ✏ = 1) applied to f (Px ) = kPxkp
p +µkPxk22. Now, Algorithm 2 with starting solution x (0) = x , applied to f finds
ex such that Aex = b and f (Pex )  f (Px ?) + in at most O ✓ p 2 µ 1/(p 2) m 1/3 R log ⇣ pmR
µ
⌘◆
calls to a linear system solver.

heading: 5.3 Logistic Regression
text: We consider the function f (Px ) = P
i log(1 + e(Px)i) which is 1-q.s.c. w.r.t its argument. We will
use Algorithm 1 with the following weight update for the width reduction step which reduces the resistance by a factor of (1 + ✏): w (t,k+1)
i w (t,k) i + 0.9✏
Theorem 5.5. For > 0, let x be the solution returned by Algorithm 1 (with ✏ = 1) applied to f (Px ) = P i log(1 + e(Px)i). Now, Algorithm 2 with starting solution x (0) = x , applied
to f finds ex such that Aex = b and P
i log(1 + e(Pex)i)  P i log(1 + e(Px ?)i) + in at most
O ✓ m 1/3 R log ⇣ mR ⌘◆ calls to a linear system solver.
Acknowledgments and Disclosure of Funding
SS is supported by a Discovery Grant awarded by NSERC (Natural Sciences and Engineering Research Council of Canada). DA is supported by a Post Graduate Doctoral Scholarship awarded by NSERC and SS’s Discovery Grant.

Review summaries:
This paper presents a framework for exactly solving optimization problems of the form $\min_{Ax=b} \sum_{i=1}^m f(x_i)$, where $f$ is a 1-dimensional quasi-self-concordant convex function, which means that its second derivative doesn't change multiplicatively by more than $O(1)$ in any interval of size $1$. Examples of quasi-self-concordant functions include the logistic loss, softmax, and $\ell_p$ regression.  The main contribution of the paper is a general algorithm for this problem that works by solving a sequence of $\widetilde{O}(m^{1/3} R \log \frac{1}{\epsilon})$ linear systems where $R = \left\Vert x^*\right\Vert_\infty$. It is based on approximately optimizing a series of $\ell_{\infty}$-constrained quadratic objectives, which is done by a width-reduced multiplicative weights approach [CKM+11] that has been previously been used for max flow, $\ell_p$ regression, and matrix scaling.

Width-reduced methods have been used to solve specific optimization problems like maximum folw and lp regression with a small number of iteration $O(m^{1/3})$. However, the design of such methods is tedious because of the need to design specific potentials and analyses. This work aims to give a unified analysis of these methods in the case of quasi-self-concordant functions. This general setting allows to consider new applications like logistic regression.

The authors give an algorithm for solving optimization problems of the form $\min_{x \in \mathbb{R}^m, Ax =b } \sum_i f( (Px)_i)$, where $A,b,P$ are given and $f$ is convex and $\textit{quasi-self concordant}$. This property, introduced by Bach in [Bac10], is an alternative notion to the standard notion of self-concordance and implies that the Hessian of f(x) is multiplicatively stable inside of a box. As several standard regression objectives (softmax, logistic loss, l_p norms) are quasi-self concordant, the study of algorithms for such objective functions is of obvious theoretical and practical importance. The previous state of the art algorithm by [CJJ+20] solves qSC regression problems in $O(m^{1/3})$ linear system solves-- this improves upon previous work of [Bac10] which achieved a complexity of $O(m^{1/2})$ . However, [CJJ+20]'s algorithm (which combines an accelerated gradient method of [MS13] with an efficient algorithm to solve trust region problems) is fairly complex and inherently requires multiple iterative loops.  The present work improves upon [CJJ+20] by providing a simple $O(m^{1/3})$-iteration algorithm for this problem, based on a framework of [CKMST11] and [EV19].