Unifying Width-Reduced Methods for Quasi-Self-Concordant Optimization
Authors: Deeksha Adil
Brian Bullins
Sushant Sachdeva
Venue: NeurIPS 2021 Poster (2021)
Keywords: Convex Optimization
Quasi-Self-Concordance
Multiplicative Weights Update
Width Reduction
Logistic Regression
Softmax

Abstract: We provide several algorithms for constrained optimization of a large class of convex problems, including softmax, $\ell_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, $\ell_p$ regression [Adil et al., SODA'19], in terms of improving the iteration complexity from $O(m^{1/2})$ to $\tilde{O}(m^{1/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 problem-specific potentials and individually tailored analyses.

As our main contribution, we initiate a new direction of study by presenting the first \emph{unified} approach to achieving $m^{1/3}$-type rates. Notably, our method goes beyond these previously considered problems to more broadly capture \emph{quasi-self-concordant} 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 $m^{1/3}$-type 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].

Unifying Width-Reduced Methods for Quasi-Self-Concordant Optimization
Deeksha Adil University of Toronto deeksha@cs, toronto.com edu
Brian Bullins
Sushant Sachdeva University of Toronto sachdeva@cs, toronto.. edu
TTI Chicago bbullins. edi
Abstract
We provide several algorithms for constrained optimization of a large class convex problems, including softmax, lp regression, and logistic regression. Central to our approach is the notion width reduction, a technique which has proven immensely useful in the context of maximum flow [Christiano et al., STOC' and, more recently, b regression [Adil et al., SODA' 19), in terms of improving the iteration complexity from (m2 to (mm//3, where m is the number of rows the design matrix, and where each iteration amounts to linear system solve. However, considerable drawback is that these methods require both problem- specific potentials and individually tailored analyses.
As our main contribution, we initiate new direction of study by presenting the first unified approach to achieving m rates. Notably, our method goes beyond these previously considered problems to more broadly capture quasi-self- concordaní losses, a class which has recently generated much interest and includes the well-studied problem of logistic regression, among others. In order do so, we develop unified width reduction method for carefully handling these losses based on a more general set of potentials. Additionally, we directly achieve m 1/3 type rates the constrained setting without the need for any explicit acceleration schemes, thus naturally complementing recent work based on a ball-oracle approach [Carmon al., NeurIPS' 20].
Introduction
We study a class of constrained optimization problems of the following form:
min Σ{((Pt))
(I)
for convex f : IR, where A E kdxn b Rd, E g with S m. Specifically, we are interested in the case where ff satisfies certain higher-order smoothness-like condition known as F.-quusi-eeff-conorddamm
Several problems of significant interest in machine learning and numerical methods meet this condition, including logistic regression [Bcc0 KSI18) as well as softmax (often used to approximate foo regression)
(q.s.c.), i.e., If (=) < Mf for all
[5e005 11
FV19
Bul20 and (regularized) bp regression [BLLI8 AKPS19]
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 ((m to 1/33,,,, and where each iteration requires linear system solve. Later work by [AKPS19] for high-accuracy Ep regression, building on an (mm-/2) -itterrtttt result from [CLLI8]. again showed
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

how width reduction could lead to improved Ó(m!/3 ) -iteration algorithms. As a drawback, however, these approaches rely on potential methods and analyses specifically tailored to each problem.
Building these results, present the first unified approach to achieving m -tyre rates, the heart of which lies a more general width reduction scheme. Notably, our method goes beyond these previously considered problems to capture quasi-self self-conccodant losses, thereby further including well-studied problems such as logistic regression, among others. By doing so, we directly achieve m -type rates in the constrained setting without relying on explicit acceleration schemes [MS13], thus complementing recent work based ball-oracle approach [CJJ+20) We additionally note that, given the ways in which our results achieve improvements similar to those of [CIJ+20], we believe our work hints at deeper, though to our knowledge not yet fully understood, connection between the techniques of width reduction and Monteiro-S acceleration.
1.1 Main Results and Applications
We first present in Section 3 width-reduced method for obtaining a crude approximation to (T) for quasi-self-concordanl f. At a high level, our algorithm returns an approximate solution ã that both satisfies the linear constraints and is bounded in &oo -norm by (RR), where R is bound on the norm of the optimal solution. Following from Theorem 3.3 the result below shows how, for the problem of (Px):
minimizing softmax (parameterized by > 0), i.e., smax, the norm of the solution by (1 + R.
log Σ
we bound
Theorem 1.1. Let x² denote the optimum of min smax, (Px). Algorithm whenn applied to
the function f(Px) = E. e (Ps), with c = v, returns such that AT = b. and
smax, (PT) < (1 + (v)))smax, (anssmaxxxP"))
in at most Ö(m 1/3
5/3) calls to a linear system solver.
As consequence of Theorem 1.1 when taking v = 2((/ log (m))) we have by Theorem 5.2
(1 + c) approximate solution to the problem of lo regression with (3 calls to linear system solver.
Further, we show the following result which can use the approximate solution returned by Theorem 1.1 initial point for achieving high-accuracy solution. We also present in Appendix A natural extension of our results to minimizing general-self-concenn
(g.s.c.) functions.
Theorem 1.2. For M-q.s.c. f, > O, and x: (0) such that Ax. and ||a:())
(
1<x S R, Algorithm
finds &t such that A = and f (x) & e f(xx)(())))))))))))))())))))ff in δ M
1/3 log M R log
)
calls 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 p(p2p=1/(0->> 1/3 R) and 0(m respectively, for jurreullarized fp 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.
1.2 Related Works
lerss--ell-conorddnece and higher-order smoothness. [Ba showed how analyze New- ton's 's method for suass-sel--ooncordant functions, with an emphasis on its application to logistic regression. Later, notions of local, Hessian, stability which follow from muasi-self-concodaant gave rise to methods with better dependence on various conditioning parameters along with linear rate of convergence KSS18 MFBR19 + In the work by KSJ18), the authors show how trust-region-bee based Newton method [W066] achieves linear convergence for locally stable functions without requiring, e.g., strong convexity. Meanwhile, after noting that quasi-self-concordee
implies Hessian stability, [CJ further improve the dependence on the distance to the optimum by lever- aging Monteiro-Svaiin acceleration [MST3, 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 oracle which minimizes a higher-ordes Taylor expansion model, though in some cases this may be relaxed to requiring linear system solves [Bul20].
Width reduction and é, regression. The notion of width is common in the multiplicative weights literature [PST95] Fleo0 GKOZ) Most of these algorithms repeatedly solve a certain subproblem. and "width" is defined as an upper bound on the lo -nom of the solution to these subproblems. The runtime of such algorithms depends linearly on the width, and since this quantity can have 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 m 13 dependence. At a high level, the idea behind the approach is to solve a sequence of weighted &g fz-miimmzzing flow subproblems, whereby 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 certain threshold, and so their weights are updated accordingly (a "width reduction" step), Several works have since adapted this approach to regression problems [CMMPI3 AAKPS 19) EV19 ABKS21] and matrix scaling [AZLOW]7] 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 2/3 iterations, which is similar
number of width reduction steps in our algorithm are restricted by e -2/3
to [VI9), but our algorithm requires e 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 lp regression using (p(mm/2-1/p) linear system solves, thus going beyond what is achievable via self-concordance. Building on this work, [AKPST9] showed how width reduction could be applied to this setting to achieve, as in the case of approximate maximum flow |CKM*11 11), similar improvement from (m2 to (m3)) (for p oo).
Further developments by [KPSWI9 AS20 for graph problems showed almost-linear time solutions for lp regression for x / /log(n) which have since been a critical part of recent advances in high-accuracy maximum flow on unit-capacity graphs [LS0 KLS20).
Accelerated methods. Recent developments by [CI++00 have shown several advantages that arise in the case of unconstrained minimization for smooth, guasi-self-coocorddeee
problems. By considering a certain ball oracle method (whereby each call to the oracle returns the minimizer of the function inside an Eg ball of radius r), [CUJ*2) 20 implement an accelerated scheme which returns a solution to the unconstrained smooth convex minimization problem in (R/r) (R/r)2/a calls to the oracle, where R is the initial l2 f2-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 E -norm of the optimum rather than the f2-norm, in the worst case, we can have | ||2 = / /m|l | a=*1 lloo, which results in both rates being essentially the same.
While the approach of |CJ++20) 20) transfers its difficulty to implementing the oracle, a key insight from their work involves showing this can be done efficiently for smooth guasi-self-concordaa functions when r is sufficiently small, where the allowed size depends on the quasi-self-concordaae 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 setting by establishing comparable rates for directly optimizing a large class of constrained convex problems without requiring smoothness of the function.
1.3 Outline of the Paper
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 (I) We then show in Section how we may attain high-accuracy solution by using the crude approximation as starting point. Here, the key idea is to considering a sequence of optimization problems inside &oo balls of manageable size, similar to [CTVV7 21J+ 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--oocorrcee applied to several problems of interest, including logistic and Ép regression.
problems, and in Section 5 we further show how our results may be
3

---

2 Preliminaries
We use boldface lowercase letters 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 for vectors refers to entry-wise inequality. Refer to the algorithm boxes for definitions of certain algorithm specific parameters that appear lemma and theorem statements.
Notation:
vector coordinate-wise, i.e. f Σ, (æ,). The notation ž y
2.1 Quasi-Self-Concordance
Definition 2.1 (g.s.c, and q.s.c.). Let R E. be a thrice differentiable function with continuous third derivative, and let > O and M > O. We say that f is (M, v)
(g.s.c.)
if
Va, Ix" (x)(
When we have the following condition:
Vx, ( < Mf"
and we call such functions M M--uass-self--oocorrtn (q.s.c.).
2.2 Problem
Recall that we are solving the following problem:
ΣF((Px)),
min Au=
where A E RRdxn b E IR. P R d < and 2 and such that f is convex, M-q.s.c. and, for 2 wp 2 O, (w,, is monotonic Vi. We can ignore the case when f" is constant since that corresponds to quadratic problem which we know how to solve directly via linear system solves.
Assumptions on the Optimum
x
We assume that E Rso such that the optimum x def
arg min Ar f (Px) satisfies
| I R.
We now define the potentials that track in the algorithm.
2.3 Potentials
Definition 2.2 (Dual Potential). For a weights vector w E Rggo we define a potential
4 (ww)
Σ (ww;) I
We also define the following corresponding potential, which gives rise to the linear regression problem that we will need solve each step of our algorithm. Definition 2.3 (Resistances and Corresponding Potential). For weights vector w E R% and > define resistances r E 18 and a corresponding potential as,
((w::) + cd(w)
ri
R
m
((r)
min Σ (PA) AA=b
We have the following relation between our two potentials and Lemma 2.4. For e > O, resistances r (Definition 2.3)) with corresponding weights w, we have
T ((r) < (1 + (
In addition, letting Pllmi = Am=b P and || ||| denote the operator norm of A, we have
( min
bb2 def ((w) L.
((r) 2
mR?2
A 2

---

3 Algorithm and Analysis for a Crude Solution for Q.S.C. Functions
In this section, we give an algorithm for solving Problem (T) crude approximation; namely, we return solution æ such that Až b. i... it satisfies the subspace constraints, and | l bounded. We will later see our applications how this translates into 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 combining multiplicative weight update (MWU) scheme with width reduction. Though such algorithms have so far only been used for f--regression, = or E [2, oo]. here we are able to extend the analysis q.s.c. functions, while also providing unified analysis for the known cases of ep-regression (refer to Section to see how we apply this algorithm to these instances). We note that we can extend this analysis other general-self-concorde functions, and we have deferred these cases to the appendix.
3.1 Algorithm and Analysis
We describe width-reduced multiplicative weight update method in Algorithm We note that the width of PA] is being reduced, though the weight updates are not entirely multiplicative. For a width step it multiplicatiie in f"(w) (lines 14-18), but for flow step (line 11) we perform a purely additive update directly on the weights.
Our proof relies on tracking two potentials, v/ (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 width reduction step in the algorithm. We next show that if our algorithm runs for at most K (m33/3) width reduction steps, then after T Õ(m 1/3) flow steps we can bound 4, Further, using the relation between & and V (Lemma 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 Width-Reduced Algorithm for M-q.s.c. Functions
procedure QSC-MWU(A, b, P. M,M, c) 0, (0,0)
2: x (000)
(#' (w) monotonic for 2 wo. x(wo) > 0)
m 1/3 2/3
3: 7 -
a θ m 11/3 2/3 2/333
4: a
5:
1=0, k = = a -M 13,
=0(m
6:
while 1 < T do
7:
(c,k)
f f"(w (wo((i)))= cD((((1)))
Resistances
R
8:
Ä
arg {PA))
> Oracle
9:
if
PÅ
I Rr then
b Flow Step
10:
(++1,)) f- (*,b) + A
11:
w ((+ f- w (t,b) + co PĀ
12:
1 - 1+1
13:
else
14:
for Indices i such that P 2 Rr do
D Width Reduction
if f non-decreasing in then
w (t.++1) is such that r (t,++1) + (1 + e)r (1,8) (1,8)
16:
17:
else
((,+1) +- Itc n (1,b) w (1.++1) is such that r
18:
19:
- t +1 return (T.A) /T
20:
We will see later how such weight/resistance changes be realized for special cases.
5

---

Changes in Y and +b
Here we show how the potentials O and v change with flow and width reduction steps, and we defer the proofs to the appendix.
Lemma 3.1. Let be as defined 2.3 After t flow steps and width reduction steps, we have,
k
62,7
((((tk))) ((((0000))
1
ff non-decreasing in w,
(1 ))2m
x²
((r((i))) S ((
if non-increasing in w.
2(1 + e)²m
Lemma 3.2. Suppose f is M.q.s.c. Let a and T be such that ot S M After I fflow steps and width reduction steps, our potential & satisfies
((w - 1 cl+ + (1+ ePPar) (1:))((11))) (1+0[++))77) (((())))))))))))))) ((w))) if non-decreasing in w,
((w(()))
2 1 c + cPaaM)) (1-((1+()7-1) ( iff" non-increasing in w.
+
Runtime Bound
We now establish the final rate of convergence for Algorithm
Theorem 3.3. Les 0, be M-q.s.c. After T S -mml/33 flow steps and K s
6 2/3) width reduction steps, Algorithm 1 returns æ such that A = b, | S
RM || (1, 1loo where (K,K) is the final weights vector that satisfies:
(T.( < ((wo)e!++s
if f" is non-decreasing in w,
(T.K) 2 D(wo)e (1+4e)
if f" is non-increasing in w.
Proof. We show the when f" is nen-decrggi function. The other case follows similarly.
We set,
+ (m 6/3 213) a - Ō m -22)))
After T= 11 Me
flow steps and = r width reduction steps, from Lemma
3.2 we have,
t (T.K) < (1 + E(1 + +o)))) T (1+ ((+(((+))=)) (ww))
K
s ((w))e (1)
s ((wo)e((+4))
We now show we cannot have more width steps. Throughout the algorithm, we have $ ((w(1.))) <
(( (+.) From Lemma 2.4 we always have To (0.00)))) 2 Φ(wo) L and T (T((KKK) < (1
c) < (1 + c)e +4 (ww)). Thus, from Lemma 3.1 we must have,
K
2T2
(1 + (e 2 (D(ww) 1
+ e Pm
From the definition of r, we note that has to be less than T for the above bound to be satisfied. Next, let (t) denote the solution of our oracle at iteration of the flow step. From the æ and w update in the algorithm,
Pž
Σ Pā (0)
caM <
Ca Σ
P
RM w (T.K) R.M.
(..........
R
This concludes proof.

---

Boosting to a High-Aceuracy Solution for Q.S.C. Functions
In this section, we give width-reduced multiplicative weights update algorithm that, given starting solution (0)) satisfying || I and Ax (0)
finds such that A= and f(Ø) & (1 + c))(()))))) for any q.s.c. function f. We would mention here that for the algorithms in this section, key that we have starting solution that satisfies our subspace constraints and has -norm bounded by R. Thus, the algorithms here may be of independent interest if such starting solution is available. We can otherwise use Algorithm with 1 to obtain such solution.
For any z, we define residual problem, and we show how it is sufficient to solve the residual problem approximately log(e-) times to obtain our high-accuracy solution. Similar approaches have been applied to specific functions such as softmax [AZLOW17] and ép-regression [AKPSI9]. 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 &o box. The difficulty lies in solving such fxc. box constraints fast. We use binary search followed by width-reduced multiplicative weights routine analogous to [CKM11] to solve our residual problem.
Definition 4.1 (Residual Problem). We define the residual objective any x. satisfying Pxx |c S R
as
res(A)= Vf(x) PA
and the residual problem as
max res(A)
A
(3)
s.t. AA = 0, and |PA =1100 I 2M
Here, z is a vector that depends on æ, and is defined as
2M +R+( E el 2M ,)],
(Px);
2M < R
R+ (P=() ZM E (0, 2M
(Px): + 2M > R
otherwise.
We note that any solution A satisfying the above box constraint satisfies |A S M-1 and Px -PPAll R.
Lemma 4.2. [Hteratvve Refinement] Let be M-q.s.c. and (1)) r-approximate solution to the residual problem at (1) (Problem Starting from x. (0 such that Ax b. [1x S R, and
iterating as (1+1) (t) e 2 after at most O RM )(=(0))((=)) ))
iterations we
get such that Ax b and f < f( +
4.1
Approximately Solving the Residual Problem
Binary Search
Lemma 4.3. Let be such that f (x((1)) - fxx") (v/2,2) and A denote the optimum of the residual problem (t). Then, res(A*) E (SMRR c²v]].
From the above lemma we may a binary search in the range ( eny. Let us start with the assumption that the residual problem has solution between (C/2. ().
Lemma 4.4. Let Ç be such that res(A*) (C/2, {] and A the optimum of the residual problem. Then, V < e.
Using Width Reduction
We will show that Algorithm returns A such that |PA 21100 S 2M and res(A) 2 200 Ç.
7

---

Algorithm 2 Boosting to e-approximation
1: procedure QSC-MIN((A A, b, P, Po M, e) such that Azo b, || x² 10 S 2R)
2: x² Zo. <- m 1/3 a <- m m/3
do 4: for E (c.f(z)) do
3: for i S logg
Decrease by 2 in each iteration
5:
for Ç E KMH v²v do De, t MWU A, P. x M, 7: x (1+1) & (0) arg min
Decrease by 2 in each iteration
6:
ve a E " y.,.)
Algorithm 3
1: procedure MWU(A, P, (,
2:
y(())
0, w0(l) C
3:
t=0
4:
A'
A P Vf
bb=10,
5: while
|w|l1 S 10 do
Â < arg min A' v E, + +M Σj 1 + ||a((0
6:
(PA 2)3
7:
T then
>> Flow Step
8:
y ((+1) (t) + A
(1+1) w 11 {aMPP -21 =1)
9:
10:
else
for Indices i such that 2M PÂ 2 do
12:
(1+1) 2w
> Width Step
1+1+1 (9)
return 1000
Lemma 4.5. Let be such that res(A*) (S/2, Algorithm returns y such that Ay 0, Py
2 20100 2M and res(y) 2 400 res( A+) in 0(m1/3 calls to a linear system solver.
We now state the main result of the section which follows directly from Lemmas 4.2 and 4.5
Theorem
4.6. For
0 M-q.s.c. function f and, x0) such that (r
| (0
1100 I R, Algorithm 2 finds & such that AT = b and f()) f(x*) s in
Mm 1/3 loogooR) log f(a(0)) ))
calls to a linear system solver.
Applications
We now show how our methods may be applied to various quasi- sen.cconorocnn functions.
5.1 Sum of Exponentials, Softmax and l. -rerression
We recall the softmax function smax, (Px) log E, which may note is 1/v-q.s.c.
We start by assuming that the optimum, for (lo( -) smax,((xx) <
We apply Algorithm Σ, (Pe) which also 1/v.q...c We can use the following weight update step for the width reduction step: w: w
(f,k+1) +- w (t.k) vlo((1 + +c.

---

Theorem 5.1. Let x² denote the optimum of min smax,(Px) Algorithm when applied to the function f(Px) = Σ. [
returns E such that A b, and
smax, (P S (1 ((v))smax, (Px"),
in al most Omm2/3 calls linear system solver.
Proof. We know that smax,
( PT) I |
+ v logmm m. From Lemma 3.3 we have that ä is
obtained in at most 13 5/3) calls to a linear system solver satisfying Ae b. Further, we
also have, P* x0 I M R]] (T.K) |1x = R |1
We will now bound [|x We note
that @ (w I (Dwo)e 2 For wo O.
(T.K)
(7,8)
(ww(T.K)
(wo)
4 (Wwoeetww
Therefore, must have w (T.K) < + 4v)y.. Our bound is
smax, (Px) S (1 + 4w) vlog m ( (1+Ō(u)) R
for 2 (11 logm), We can now do a binary search on R as follows to obtain
smax, (PT) S Ö(v))smax,
Binary search on R: Let Ro denote the value |x Ro- Now, for any R 2 Ro, attain an which has an objective value at most R(1 + 4v). For any R < Rg. as long as such that the plane Az has least point with infinity norm most R, will get feasible solution to our problem. However, the objective value guarantee is Ro. the solution returned in such cases must give objective value larger than Rg- We thus do a binary search on R and reach (v) close to the value Rg. This will require running our algorithm (log(R Ry 1)) times. the end we can return the æ which gives the smallest objective values among all these runs.
R(1 + 4v) may not hold. Since the optimum
Theorem 5.2. Let x² denote the optimum of the 8o regressioo problem, min || Px lc. Algo- (Pa);
rithum when applied to the function (PPx) Σ. + such that Aø and
(Pe), for = 8 log
returns T
| 0c
in at most 13 - calls to a linear system solve.
Theorem 5.3. For >
be the solution returned by Algorithm (with 1) applied to f(Px) E. (Pz), Now; Algorithm 2 with starting solution x!!)) T, applied f finds x such
that A b and E,e (P3);
(Px")s in most O 0mm R2 log(())) (")) calls
< (1 E.e.
linear system solver.
5.2 p-Norm Regression
We will solve, of | pu| for p 2
3 which pn 1/(p-2)-q.s.. -.s.c. w.r.t. its argument. We first apply Algorithm 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; (l,k+1) + (1 + e) 1/(x=2) (t.k)
Theorem 5.4. For > 0 and p p2>22 3, let a be the solution returned by Algorithm with 1) applied to ((r)) Pm |==1] +/] Pa: Now, Algorithm with starting solution x: (0) ac, applied to finds
such that A = b and ((Pm) S f(Px*) + 5 in at most O pp2x 1/(1p-0p----0pp m 2log calls linear system solver.

---

5.3 Logistic Regression
We consider the function f P2)) E, lo c( which 1-q.s.c. war its argument. We will use Algorithm with the following weight update for the width reduction step which reduces the resistance by factor of +1++3 E): w. (t,k+l)
+ w w (1.b) 0.9c
Theorem 5.5. For å 0, let I be the solution returned by Algorithm 7 (with 1) applied
to f(Px) Σ, log(1 + el Now, Algorithm 2 with starting solution x0)) x. applied
to f finds x such that A b and Σ, log(1 + clPE))) < Σ, log(1 + e(px))) + in at most
m 1/3 ml/3Rlog 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 Post Graduate Doctoral Scholarship awarded by NSERC and SS's ' Discovery Grant.
10

---

References
[ABKS21] Deeksha Adil, Brian Bullins, Rasmus Kyng, and Sushant Sachdeva. Almost-liner--imee weighted e--norm solvers in slightly dense graphs via sparsification, 2021.
[AKPS19] Deeksha Adil, Rasmus Kyng, Richard Peng, and Sushant Sachdeva. Iterative refine- ment for f--norm regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1405-1424. SIAM, 2019.
[AS20] Deeksha Adil and Sushant Sachdeva. Faster p-norm minimizing flows, via smoothed q-norm problems. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 892-910. SIAM, 2020.
[ASSI9] Yossi Arjevani, Ohad Shamir, and Ron Shiff. Oracle complexity of second-order methods for smooth convex optimization. Mathematical Programming, 178(1):3277 360, 2019.
[AZLOW17] Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. Much faster algorithms for matrix scaling. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 890-901. IEEE, 2017.
[Bac10] Francis Bach. Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4:384-414, 2010.
[BCLL18] Sébastien Bubeck, Michael B Cohen, Yin Tat Lee, and Yuanzhi Li. An homotopy method for ip regression provably beyond self cefeorocceeeece and in input-sparsity time. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. pages 1 1130-1133 137, 2018.
[Bul20] Brian Bullins. Highly smooth minimization of non-smooth problems. In Conference Learning Theory, pages 988-908-33 10380. PMLR, 2020.
[C]]+20] Yair Carmon, Arun Jambulapati, Qijia Jiang. Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian. Acceleration with a ball optimization oracle. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 19052-19063. Curran Associates, Inc., 2020.
[CKM*1] 11] Paul Christiano, Jonathan A Kelner, Aleksander Madry, Daniel A Spielman, and Shang-Huz Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 273-282,20 2011.
[CMMP13] Hui Han Chin, Aleksander Madry, Gary L Miller, and Richard Peng. Runtime guaran- tees for regression problems. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 269-282, 2013.
[CMTV17] Michael B Cohen, Aleksander Madry, Dimitris Tsipras, and Adrian Vladu. Matrix scaling and balaneing via box constrained newton's 's method and interior point methods. In 2017 7 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 902-913. IEEE, 2017.
[EV19] Alina Ene and Adrian Vladu. Improved convergence for é and foo regression via iteratively reweighted least squares. In International Conference on Machine Learning, pages 1794-1801. PMLR, 2019.
[Fce00] Lisa K Fleischer. Approximating fractional multicommodity flow independent of the number of commodities. SIAM Journal on Discrete Mathematics, 13(4)5005-520 2000.
[GDG+ 19] Alexander Gasnikov, Pavel E. Dvurechensky, Eduard A. Gorbunov, Evgeniya A. Vorontsova, Daniil Selikhanovych. César A. Uribe, Bo Jiang, Haoyue Wang, Shuzhong Zhang. Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. Near optimal methods for minimizing convex functions with lipschitz p-th derivatives. In COLT, pages 1392-1393, 2019.

---

[GK07] Naveen Garg and Jochen Könemann. Faster and simpler algorithms for multicom- modity flow and other fractional packing problems. SIAM Journal on Computing. 37(2):630 652, 2007.
[KLS20] Tarun Kathuria, Yang P Liu, and Aaron Sidford. Unit capacity maxflow in almost m 4/3 time. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 119-130. IEEE, 2020.
[KPSW19] Rasmus Kyng, Richard Peng, Sushant Sachdeva, and Di Wang. Flows in almost linear time via adaptive preconditioning. In Proceedings of the 51 Anmual ACM SIGACT Symposium on Theory of Computing, pages 902-913, 2019.
[KSJ18] Sai Praneeth Karimireddy, Sebastian Stich, and Martin Jaggi. Global linear con- vergence of newton's s method without strong-convexity or lipschitz gradients. arXiv preprint arXiv: 00413, 2018.
[LS20]] Yang Liu and Aaron Sidford. Faster energy maximization for faster maximum flow. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, pages 803-814, 2020.
[MFBRI9] Ulysse Martcau- Fereay, Francis Bach, and Alessandro Rudi. Globally convergent newton methods for ill-conditioned generalized self-concordant losses. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[MS13] Renato DC Monteiro and Benar Fux Svaiter. An accelerated hybrid proximal extragra- dient method for convex optimization and its implications to second-order methods. SIAM Journal on Optimization, 23(2):1092-112 -125, 2013.
[Nes05] Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical program- ming, 103(1):127-152, 2005.
[NW06] Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.
[PST95] Serge A Plotkin, David Shmoys, and Éva Tardos. Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research, 20(2):257-301, 1995.
[STD19] Tianxiao Sun and Quoe Tran-Dinh. Generalized self cofoorannndd functions: a recipe for newton-type methods. Mathematical Programming, 178(1):145-21) 2019.
12


Reviews:
[{"review_id": "T3uSD2IXmXe", "reviewer": "Reviewer_wfoS", "summary": "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.\n\nThe 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem studied is fundamental and important, as can be witnessed by the fact that it contains logistic regression as a special case. On the other hand, the fact that it has an $O(m^{1/3})$ runtime overhead might make it less intriguing to the machine learning community. This could be mitigated if it were accompanied by numerical experiments that would show that this $m^{1/3}$ doesn't arise in practice, but currently there is no evidence that this is the case.\n\nWhile the general ideas presented are not new and have arisen in previous work, the authors aim to unify all of these approaches by presenting a general all-encompassing analysis. This is a worthy goal, although currently I cannot say that the writing of the paper is clear enough to warrant the status of a go-to reference for the width-reduction approach. In particular, the intuition (both high-level and technical) behind the analysis could be explained much better. In this paper a clearer comparison to previous work, with clean explanations and proofs would go a long way.\n\nSpecific comments:\n\n* I would expect to have seen a comparison of the authors' analysis to that of [AZLOW17] for matrix scaling. In fact, it seems to me that the approach is exactly the same: take $\\ell_\\infty$-constrained steps by using width-reduced multiplicative weights update. What are the technical differences (e.g. significant simplifications in the analysis)? The authors should definitely elaborate on this.\n\n* For clarity, the use of the potentials $\\Phi$ and $\\Psi$ should be explained. Also, what do their changes mean for the algorithm?\n\n* Page 6 contains a number of technical lemmas but no explanation on each of them.\n\n* The objective function in Section 5.2 does not seem quasi-self-concordant to me. The second derivative is $p(p-1) (Px)^{p-2}$ which can be as much as $p(p-1) R^{p-2}$. As the problem is constrained, the $\\ell_2$ regularization term doesn't necessarily help in making $R$ small (e.g. I can scale down $A$ and $b$ in the linear system $Ax=b$ to force $R$ to be arbitrarily large) \n\n* For $\\ell_\\infty$ regression, how does the authors' approach compare to that of e.g. [EV19], who obtain a better error dependence?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "FkoDjuTXX0Q", "reviewer": "Reviewer_JKQc", "summary": "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.\n\nThe 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]. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This analysis is well written. and extends the scope of problems iterative refinement-least squares approaches can solve significantly (previous work on this area has focused on $\\ell_p$-norm, softmax, and logistic regression) to the set of all qSC functions. The authors do this by a clever extension of previous techniques-- this allows them to incorporate second derivative information about the function $f$ in the least-squares problems they solve in each iteration. Further, the approach suggested here may achieve significant practical performance gains over previous work (IRLS approaches have been very successfully used for various regression tasks in practice, and converge much faster than the theoretical iteration bounds would indicate). ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Although the algorithm obtains an alternative to [CJJ+20] which matches the $O(m^{1/3})$ iteration complexity for quasi-self concordant optimization, its theoretical guarantee is still inferior even for the restricted case of qSC functions considered in this paper. For the important special case of softmax regression, the algorithm here obtains a $(1+\\nu)$-approximate solution in $O(m^{1/3} \\nu^{-5/3})$ iterations-- the result of [CJJ+20] uses $O(m^{1/3} \\nu^{-2/3})$ iterations. This gap is surprising, as the algorithm of [EV19] (which the paper borrows heavily from) achieves  $O(m^{1/3} \\nu^{-2/3})$ iterations for the related problem of $(1+\\nu)$-approximate $\\ell_\\infty$ regression. Some discussion of why this gap exists (or an improved analysis which closes this gap) would strengthen the result significantly. \n\nIn addition, the algorithm of [CJJ+20] actually achieves a stronger result: the iteration complexity improves if the $2$-norm of the optimal solution $x^\\star$ is small. Does the algorithm given here achieve a similar result? \n\nFinally, the algorithm given more than superficially resembles the IRLS procedure of [EV19]. I would appreciate some discussion of the ideas borrowed from previous work in the introduction.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "9omdytOHvl6", "reviewer": "Reviewer_J1te", "summary": "The paper provides novel, simpler algorithms that match (or come close to matching) the best known results for the minimization of linearly constrained problems of the form $\\min_{Ax = b} \\sum_i f((Px)_i),$ where $f$ is convex, quasi-self-concordant and $\\Px^*|_\\infty \\leq R$ for the optimum solution. The main contribution is the extension of width-reduction techniques, that previously were confined to l_p-regression problems, to this more general class.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The strength of this paper relies in its originality, i.e., applying width-reduction techniques to a much wider class of problems than previously done, quasi-self-concordant function.. It is nice that this can be done in a unified way. On the other hand, one would hope that a unified presentation of this approach would allow for some simplification and abstraction of the fundamental steps. On the contrary, the paper feels like a lifting of CKM+11 to a much more general setting without much additional understanding of the width-reduction phenomenon. \nSpecifically, it would be nice if the authors better motivated the significance of the second derivatives of $f''$, which appears to replace the natural generalization of the MWU of CKM+11, which would be $f'$.\n\nMore generally, the paper suffers from a lack of clarity that makes it very difficult to approach for readers well-versed in optimization, but not very familiar with precedent results. For instance, I am very familiar with the seminal result of CKM+11, on which the paper approach is based, but had a very hard time reconciling my knowledge with the current paper because of the poor presentation. Specific points that need to be clarified include:\n- make the application of width reduction explicit: in the current version of the paper, the authors do not even mention which variables are performing MWU (presumably the $f''(w)$) and which width is being reduced (that of the flow P\\Delta). This clarification would immediately motivate the introduction of the potential function $\\Phi.$\n- the dual potential CKM+11 is also poorly motivated and should be directly related to typical dual quantities, just as was done in CKM+11. While this is implicitly done in Lemma 2.4, its current presentation remains fairly obscure.\n\nMinor Issues:\n- Theorem 5.1 and line 53 appear to use two different notions of the variable $\\epsilon$\n- line 134: clarify the introduction of the coordinate-wise monotonic property for $f''$.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors should provide a closer comparison to CJJ+20 in terms of running times. The dependence on the norm of the optimum solution appears to be different there.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "75gkUrOhmmX", "reviewer": "Reviewer_NMEA", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is quite technical and assume a good knowledge of previous works. The theoretical results are well stated and seems strong. However, I am not familiar enough with width-reduced methods to be able to check the results.\n\nThe quality of the writing is good but I found a lack of informal explanations and motivations of the setting. I am certain to find them in the references given but it would be great to recall them. I hope the following remarks will help to improve the clarity of the paper to non-experts.\n\n- What is the main idea of reduced methods in a simple setting like maximum flow ? In this abstract setting is not even obvious why it is called \"with-reduced\".\n- Why this method first developed for maximum flow is suitable for other settings which seems quite different like logistic regression ?\n- What is the intuition behind those potential functions ?\n- The use of big O in algorithms is a bit weird. Can't you give a precise value for tau and alpha ?\n- I understand that the motivation to go from $O(m^{1/2})$ to $O(m^{1/3})$ in terms of number of call to a linear solver is important in some problems like maximum flow. However, it is quite unusual in logistic regression for example. Is it still a good way to measure computational complexity ? Could you compare to other work considering logistic regression optimization like (Marteau-Ferey 2019) ?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers and area chair agree that the technical contribution of the paper is significant as it yields a simpler algorithm for an important class of problems and extends the applicability of the width-reduced approach of [CKM+11]. The main weakness of the paper is the lack of clear explanations behind the technical analysis and comparison with existing similar methods.  However, the authors have addressed the reviewers' questions and provided some explanation in the rebuttal phase. Assuming these explanations will find their way in the final version, I believe the submission should be accepted.
Decision: Accept (Poster)